堆结构与堆排序

堆结构

堆结构的逻辑结构和完全二叉树一样（一般我们都用数组来实现堆和完全二叉树），不过堆结构根节点与子节点有大小关系。

小根堆：根节点的值小于或等于子节点的值
大根堆：根节点的值大于或等于子节点的值

下图中就是一个典型的小根堆：

在这里插入图片描述

我们发现，小根堆的根节点值一定是整个堆中最小的，并且和完全二叉树一样，根节点与子节点的下标是有计算公式的：

//整个堆的根节点下标为0
if 某节点的下标为i:左子节点下标为2*i + 1右子节点下标为2*i + 2其父节点下标为(i-1) / 2

堆的大小（堆中元素的个数）由变量 $s i ze$ 来维护，如果下标不再 $[0, s i ze]$ 范围内，说明无此节点。

大根堆与小根堆同理，我们也来看一个典型的大根堆：
在这里插入图片描述

讲到数据结构，除了了解最基本的存储数据形式，还要熟悉属于此数据结构的增删查改操作，下面以大根堆为例来细说堆结构的四大操作：

大根堆的增删查改以及向上调整、向下调整：

往大根堆中插入数据：

我们在堆中插入数据有一套固定的流程，先在堆的最底部（也就是实现堆的数组的最右端）插入新元素，判定新元素插入后与根节点之间符不符合大小关系，如果不符合就将此元素向上调整。

void insert(int num, int Size)
{heap[Size++] = num;// 末端插入新元素之后需要向上调整int cur = Size - 1;         // num对应的下标int parent = (cur - 1) / 2; // 父节点下标while (cur > 0 && num > heap[parent]){swap(cur, parent);cur = parent;parent = (cur - 1) / 2;}
}

其实代码后半段就是对末端元素进行向上调整，为方便对任意位置 $i$ 进行向上调整，我们可以给出向上调整函数：

void UpAdjust(int heap[],int i,int Size){int cur = i;int parent = (cur-1) / 2;while(heap[cur] > heap[parent]){//交换父子节点int temp = heap[cur];heap[cur] = heap[parent];heap[parent] = temp;cur = parent;parent = (cur-1) / 2;}   
}

大根堆中弹出数据：

弹出数据也是按照流程来，先将根部数据弹出，再将堆末端的数据放到堆的顶部，之后从顶部开始向下调整。

int pop()
{if (Size == 0)return -1;int ans = heap[0];heap[0] = heap[--Size];int cur = 0;while (2 * cur + 1 <= Size - 1){int largest = cur;int leftChild = 2 * cur + 1;int rightChild = 2 * cur + 2;//比较左子节点if(heap[leftChild] > heap[largest]){largest = leftChild;}//比较右子节点if(rightChild <= Size - 1 && heap[rightChild] > heap[largest]){largest = rightChild;}if(largest = cur)break;swap(cur, largest);cur = largest;}return ans;
}

代码后半段是向下调整，我们同样整理出 $i$ 位置的向下调整函数：

void DownAdjust(int heap[],int i,int Size){if(i >= Size) return;int cur = i;int leftChild = 2 * cur + 1;int rightChild;while(leftChild <= Size - 1){int largest = cur;leftChild = 2 * cur + 1;rightChild = 2 * cur + 2;//比较左子节点if(heap[leftChild] > heap[largest]){largest = leftChild;}//比较右子节点if(rightChild <= Size - 1 && heap[rightChild] > heap[largest]){largest = rightChild;}if(largest = cur)break;int temp = heap[cur];heap[cur] = heap[largest];heap[largest] = temp; cur = largest;}
}

堆排序

前面我们详细分析了堆的逻辑结构，尤其是大根堆的性质和常用函数。现在就到了【学以致用】的阶段了，仔细想想，如果我把一堆数都放在最大堆中，堆顶是不是就是最大的数，我把堆顶取出来，是不是就拿到了这堆数的最大值，我们继续这个思路。

缺数堆（就是被拿走堆顶的残堆，缺数堆更简洁形象）之后会自动转换成一个新的大根堆，我再取堆顶，是不是就拿到了第二大的数，这样循环往复，我们就得到了一个从大到小排列的数字序列。

根据这个思路我们可以得到一种新的排序方法 —— 堆排序

void heapSort(int &arr[],int N){//在数组基础上原地建大根堆for(int i = 0;i < N;i++){heapInsert(arr, i);}//将堆顶与末端交换，这样末端就是大的值for(int i = N-1; i >= 1;i--){int temp = arr[0];arr[0] = arr[i];arr[i] = temp;DownAdjust(arr,0,i+1);}
}

void heapInsert(int arr[],int oldSize){int cur = oldSize;int parent = (cur-1) / 2;while(arr[cur] > arr[parent]){int temp = arr[cur];arr[cur] = arr[parent];arr[parent] = temp;}
}
void DownAdjust(int arr[],int cur,int size){int leftChild = 2*cur + 1;int rightChild;int largest;while(left <= size - 1){leftChild = 2*cur + 1;rightChild = 2*cur + 2;largest = cur;//比较左子节点if(arr[leftChild] > arr[largest]){largest = leftChild;} //比较右子节点if(rightChild <= size-1 && arr[rightChild] > arr[largest]){largest = rightChild;}if(cur == largest)	break;int temp = arr[cur];arr[cur] = arr[largest];arr[largest] = temp;cur = largest;}
}