建堆、堆排序

     我们前面已经了解过什么是堆，现在我们来根据它的特征来研究如何建一个堆。

1.建堆

图解思路

初始化，申请空间，给堆赋值

代码实现 typedef int Datatype; //创建堆的结构体 typedef struct Heap { Datatype* array; int capacity; int size; }Heap; //初始化堆 void InitHeap(Heap* hp,Datatype* array, int size) { assert(hp); hp->array = (Datatype*)malloc(sizeof(Datatype)* size); if (hp->array == NULL) { return; } hp->capacity = size; for (int i = 0; i < size; i++) { hp->array[i] = array[i]; } hp->size = size; //调整该二叉树;使其满足堆的性质 //找倒数第一个非叶子节点,开始向下调整,调用AdjustDown int leaflast = ((size - 2) >> 1); for (; leaflast >= 0;leaflast--) { AdjustDown(hp->array, size, leaflast); } } //交换 int Swap(int* a,int* b) { int tmp; tmp = *a; *a = *b; *b = tmp; } //向下调整 void AdjustDown(Datatype* array, int size, int parent) { int child = parent * 2 + 1; //默认标记左孩子 while (child < size) { //找左右孩子中的小孩子,右孩子要想存在 if (child+1<size && array[child + 1] < array[child]) { child += 1; //右比左小 child标记的小孩子更换 } if (array[child] < array[parent]) { Swap(&array[child], &array[parent]); parent = child; child = parent * 2 + 1; } else { return; } } }

     以上，我们的堆已经建成功，如果需要建大堆，我们可以左右孩子中的较大的孩子，与父母做出比较 ，判断是否需要交换。      

2.堆排序

     那么如何利用堆的结构实现排序的功能。首先，将$N$个元素建堆,如果升序排列建大堆，降序排列建小堆。然后将堆顶元素与最后一个元素交换，在将剩下的元素重新调整得到满足堆的新的堆顶元素，重复之前的步骤，每次元素的数量减一。最后，就可以得到我们要求的序列。

代码实现 //为实现排序调整堆(向下调整) void HeapAdjust(int* array,int size,int parent) { int child = parent * 2 + 1; //默认标记左孩子 while (child < size) { //找左右孩子中的小孩子,右孩子要想存在 if (child + 1 < size && array[child + 1] < array[child]) { child += 1; //右比左小 child标记的小孩子更换 } if (array[child] < array[parent]) { Swap(&array[child], &array[parent]); parent = child; child = parent * 2 + 1; } else { return; } } } //排序 void HeapSort(int* array, int size) { //找倒数第一个非叶子节点,得到小堆 int leaflast = ((size - 2) >> 1); for (; leaflast >= 0; leaflast--) { HeapAdjust(array, size, leaflast); } //堆顶元素与最后一个元素交换,再调整 int end = size - 1; while (end) { Swap(&array[0], &array[end]); HeapAdjust(array, end, 0); end--; } }

     时间复杂度：$NlogN$      以上，实现了降序的排列方式，若要实现升序，只需要建立大堆即可。

3.堆的应用

      TOP k 问题:在$N$个数据中找最大的或者最小的前$k$个元素。求最大建小堆,求最小建大堆。（此处以找最大的前K各元素为例） 具体做法:

先遍历得到前$k$个元素，建立堆。用剩下$N-k$个元素与堆顶元素比较，比堆顶大就替换，比堆顶小就丢弃，再调整当前堆， 直到结束，就找到了最大的前$K$个元素。

     时间复杂度$NlogK$