1.堆的概念和结构
堆的逻辑结构是完全二叉树。
逻辑结构的视角观察：
在大根堆中，双亲节点大于孩子节点；
在小根堆中，双亲节点小于孩子节点。
堆的存储结构是一维数组。
存储结构的视角观察（设数组K）：
在小根堆中：K[i]<=K[2*i+1] && K[i]<=K[2*i+2]；
在大根堆中：K[i]>=K[2*i+1] && K[i]>=K[2*i+2]
2.堆的实现
2.1向上调整算法
向上调整算法的前提是祖先是堆。
以小堆为例：
1.给定向上调整的起点（孩子节点下标），根据起点下标计算双亲节点下标。
孩子节点与双亲结点间的下标关系：
child=parent*2+1 || child=parent*2+2;
parent=(child-1)/2;
2.比较孩子节点与双亲节点数值大小，若孩子节点小于双亲节点，则交换两者，并将孩子节点的下标更新为之前的双亲节点下标，根据最新的孩子节点下标重新计算双亲节点下标，重复这一过程直到孩子节点为根节点。
代码实现：
//向上调整 void Adjustup(HPDataType* a,int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] < a[parent])//建小堆 { Swap(&a[child], &a[parent]); child = parent; parent = (parent - 1) / 2; } else { break; } } }
2.2向下调整算法
向下调整算法的前提是左右子树是堆。
以小堆为例：
1.给定向下调整的起点（双亲节点下标）和节点总数，根据起点下标计算孩子节点下标。
注意：向下调整时，若有两个孩子节点，则需要确保调整的是较小的孩子节点。
2.比较孩子节点与双亲节点数值大小，若孩子节点小于双亲节点，则交换两者，并将双亲节点的下标更为之前的孩子节点下标，根据最新的双亲节点下标重新计算孩子节点下标，重复这一过程直到孩子节点超出节点总数。
代码实现：
//向下调整 void Adjustdown(HPDataType* a, int n,int parent) { int child = parent * 2 + 1; while (child < n) { if (child+1<n && a[child+1] < a[child])//建小堆 { child = child + 1; } if (a[child] < a[parent])//建小堆 { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }
2.3堆的创建
堆的创建既可以使用向上调整算法，也可以使用向下调整算法。
1.向上调整算法建堆
由于向上调整算法的前提是祖先是堆，所以我们需要从第二个节点开始向上调整（即根节点的下一个）。
代码实现：
for(int i = 1; i < n; i++) { Adjustup(a,i); }
2.向下调整算法建堆
由于向下调整算法的前提是左右子树是堆，所以我们需要从倒数第一个非叶子节点向下调整。
已知节点总数为n，那么倒数第一个节点的下标即为n-1，该节点的双亲节点下标即为(n-1-1)/2，该双亲节点就是倒数第一个非叶子节点（因为堆是完全二叉树）。
代码实现：
for (int i = (n - 2) / 2; i >= 0; i--) { Adjustdown(a,n,i); }
2.4建堆时间复杂度
假设树的高度为h。
1.向上调整建堆时间复杂度
则需要移动节点总的移动步数为：
即向上调整建堆的时间复杂度为O(N*log₂N)。
2.向下调整建堆时间复杂度
则需要移动节点总的移动步数为：
即向下调整建堆的时间复杂度为O(N)。
2.5堆的插入
首先尾插到该数组，再向上调整即可。
2.6堆的删除
删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据交换，然后删除数组最后一个数据，再进行向下调整算法。
2.7堆的代码实现
// 堆的构建 void HeapCreate(Heap* hp, HPDataType* a, int n) { assert(hp); assert(a); hp->a = (HPDataType*)malloc(sizeof(HPDataType)*n); if (hp->a == NULL) { perror("malloc fail"); exit(-1); } hp->capacity = hp->size = n; memcpy(hp->a, a, sizeof(HPDataType) * n); for (int i = 1; i < n; i++) { Adjustup(hp->a, i); } } // 堆的销毁 void HeapDestory(Heap* hp) { assert(hp); free(hp->a); hp->a = NULL; hp->capacity = hp->size = 0; } // 堆的插入 void HeapPush(Heap* hp, HPDataType x) { assert(hp); assert(hp->a); //1.检查容量 if (hp->size == hp->capacity) { int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2; HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) *newCapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } hp->a = tmp; hp->capacity = newCapacity; } hp->a[hp->size] = x; hp->size++; Adjustup(hp->a, hp->size-1); } // 堆的删除 void HeapPop(Heap* hp) { assert(hp); assert(hp->size > 0); Swap(&hp->a[0], &hp->a[hp->size - 1]); --hp->size; Adjustdown(hp->a, hp->size, 0); } // 取堆顶的数据 HPDataType HeapTop(Heap* hp) { assert(hp); assert(hp->a); return hp->a[0]; } // 堆的数据个数 int HeapSize(Heap* hp) { assert(hp); return hp->size; } // 堆的判空 bool HeapEmpty(Heap* hp) { assert(hp); return hp->size == 0; }
3.堆的应用
3.1堆排序
方法1：
首先，我们当然可以利用已经堆这一数据结构进行输出有序的数据。
以升序为例：
首先构建小堆，然后输出堆顶元素，再Pop，再向下调整，循环执行此步骤直到堆空。
代码实现：
void HeapSort(int* a, int n) { HP hp; HeapInit(&hp); for (int i = 0; i < n; i++) { HeapPush(&hp, a[i]); } int i = 0; while (!HeapEmpty(&hp)) { //printf("%d ", HeapTop(&hp)); a[i++] = HeapTop(&hp); HeapPop(&hp); } HeapDestroy(&hp); }
但这样有很明显的缺点：
1.需要堆这样一个数据结构，构建麻烦；
2.空间复杂度的消耗。
方法2：
以升序为例：
首先构建大堆（推荐使用向下调整），此时堆顶元素一定为最大值，然后将堆顶元素与最后一个节点交换，此时最大值就放到了整个数组的最后面，然后除了最后一个值以外，其他的数据再向下调整，调整完成后堆顶元素为次大值，再与数组倒数第二个位置的值交换，这样依此往复就得到了升序数组。
注意：
升序建大堆，降序建小堆。
代码实现：
void HeapSort(int* a, int n) { // 向上调整建堆 （大堆）or （小堆） // O(N*logN) /*for (int i = 1; i < n; i++) { AdjustUp(a, i); }*/ // 向下调整建堆 // O(N) for (int i = (n-1-1)/2; i >= 0; i--) { AdjustDown(a, n, i); } // O(N*logN) int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } }
3.2TopK问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。
最佳的方式就是用堆来解决，基本思路如下：
1.用数据集合中前K个元素来建堆
- 前k个最大的元素，则建小堆
- 前k个最小的元素，则建大堆
2.用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
首先可以写一段生成随机数字的程序，并将这些数字写入到文件中。
void CreateNDate() { // 造数据 int n = 10000000; srand(time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return; } for (int i = 0; i < n; ++i) { int x = (rand() + i) % 10000000; fprintf(fin, "%d\n", x); } fclose(fin); }
根据上面分析的思路完成代码。
void PrintTopK(const char* filename, int k) { // 1. 建堆--用a中前k个元素建堆 FILE* fout = fopen(filename, "r"); if (fout == NULL) { perror("fopen fail"); return; } int* minheap = (int*)malloc(sizeof(int) * k); if (minheap == NULL) { perror("malloc fail"); return; } for (int i = 0; i < k; i++) { fscanf(fout, "%d", &minheap[i]); } // 前k个数建小堆 for (int i = (k-2)/2; i >=0 ; --i) { AdjustDown(minheap, k, i); } // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换 int x = 0; while (fscanf(fout, "%d", &x) != EOF) { if (x > minheap[0]) { // 替换你进堆 minheap[0] = x; AdjustDown(minheap, k, 0); } } for (int i = 0; i < k; i++) { printf("%d ", minheap[i]); } printf("\n"); fclose(fout); }
堆处理大量数据的速度非常快，我们都知道对数的特性，所以堆处理大量数据的能力非常强。在遇到TopK问题或者大量数据排序时，可以考虑使用堆排序。
