2.2堆的实现
在介绍了堆的概念以及它的存储模式之后，那么我们如何建堆呢？
通常建堆有两种模式：向上调整建堆和向下调整建堆。我们以建小根堆为例来介绍这两种建堆模式，先来介绍向上调整建堆的模式。
①向上调整建堆
向上调整建堆的基本模式与原理：
1、先将元素插入到堆的末尾，即最后一个孩子之后。
2、插入之后如果小根堆或者大根堆的性质遭到破坏，就将新插入的节点顺着双亲往上调整到合适位置。
向上调整原理图：
代码实现：
void AdjustUp(int* a, int child) { while (child>0) { int parent = (child - 1) / 2; if (a[child] < a[parent]) { //建小根堆 Swap(&a[child], &a[parent]); child = parent; } else { break; } } }
②向下调整建堆
向下调整建堆和向上调整建堆不同的是，它需要左右子树必须是一个堆才能调整。
图解过程：
代码实现：
void AdjustDown(HPDataType* a, int size, int parent) { int maxchild = parent * 2 + 1; while (maxchild<size) { if (maxchild+1<size&&a[maxchild] < a[maxchild + 1]) { maxchild++; } if (a[parent] < a[maxchild]) { Swap(&a[parent], &a[maxchild]); parent = maxchild; maxchild = parent * 2 + 1; } else break; } }
2.3时间复杂度
向上调整建堆：
向下调整建堆：
通过比较我们发现向上调整和向下调整建堆各有优劣：
1、向上调整建堆不需要任何条件即可建堆，而向下调整建堆则需要左右子树本身就是大根堆或者小根堆。
2、向下调整建堆的时间复杂度远小于向上调整建堆，原因也很简单，向下调整建堆最后一层节点不需要向下调整，而这一部分的节点几乎占了一半的节点，而向上调整建堆仅仅是根节点没有调整，所以时间复杂度向下调整要优于向上调整。
我们是优先选择向下调整建堆的，但是它是有限制的，如果我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点，就可以调整成堆。
例如：
三、堆的应用
3.1堆排序
我们学习过比较简单的冒泡排序，今天主要想介绍一下堆排序。
大根堆和小根堆分别可以选出最大的数和最小的数，而且我们前面已经证实向下调整算法明显优于向上调整，所以我们的堆排序也以向下调整来写的一个算法。
那么我们堆排序的基本思想是什么呢？
1、如果我们以升序为例，选用小根堆，选出最小的数排在首位，剩下数据看作堆，这时候的问题就是双亲与子的关系就全乱了，只能重新建堆，如果每个数都这样排序，建堆，那么时间复杂度是0(N^2)，也就和冒泡排序半斤八两了，显然堆排序的优势就荡然无存。
2、如果我们换一种思维，我们不能抛弃向下调整的优势，又要排出有序的数组，我们采用交换的方式，如果我们排升序，那么选用大根堆是极好的，我们怎么做呢？
①选出最大的数，然后和最后一个数交换，这时最后那个数来到首位
②对第一个数进行向下调整算法(但是最后一个数不参加向下调整)，因为它的左右子树满足大根堆，是可以调整的，一次调整选出最大的数排在末尾，第二次就选出次大的数，依此类推。每个数进行向下调整，时间复杂度是0(N*logN)。大大优化。
void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } void AdjustDown(int* a, int size, int parent) { int maxchild = parent * 2 + 1; while (maxchild < size) { if (maxchild + 1 < size && a[maxchild] < a[maxchild + 1])//右孩子要小于size { maxchild++; } if (a[parent] < a[maxchild]) { Swap(&a[parent], &a[maxchild]); parent = maxchild; maxchild = parent * 2 + 1; } else break; } } void HeapSort(int* a, int n) { //向下调整建堆 for (int i = (n - 2) / 2; i >= 0; --i) { AdjustDown(a, n, i); } int i = 1; while (i < n) { Swap(&a[0], &a[n - i]); AdjustDown(a, n - i, 0); ++i; } } void PrintArray(int* a, int size) { for (int i = 0; i < size; i++) { printf("%d ", a[i]); } printf("\n"); } int main() { int a[] = { 10,20,45,32,66,17,22,36,76 }; int N = sizeof(a) / sizeof(int); HeapSort(a,N); PrintArray(a,N); return 0; }
3.2TopK问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
若求前K个最大的元素，则建小堆‘；
若求前K个最小的元素，则建大堆。
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素。将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
简单来说就是，我们不将全部数据导入堆，因为这样不仅耗时而且对于内存是极大的占用。如果要求找前K个最大或者最小的数，我们只作一个小堆，把前K个元素导入堆。
如果求前K个最小的元素：我们建大根堆，根是这K个数里最大的数，如果有数比根还要小，就让这个数顶替根，然后调整根，求前K个最大的数与之类似。
基于这样一个理念，我从一个文件导入100000个随机数，选出其中10个最大或最小(自己调整)的数。
代码实现：
void Swap(HPDataType* a, HPDataType* b) { HPDataType tmp = *a; *a = *b; *b = tmp; } void AdjustDown(HPDataType* a, int size, int parent) { int minchild = parent * 2 + 1; while (minchild < size) { if (minchild + 1 < size && a[minchild] > a[minchild + 1])//右孩子要小于size { minchild++; } if (a[parent] > a[minchild]) { Swap(&a[parent], &a[minchild]); parent = minchild; minchild = parent * 2 + 1; } else break; } } void CreateDataFile(const char* filename, int N) { FILE* fin = fopen(filename, "w"); if (fin == NULL) { perror("fopen fail"); return; } else { srand(time(0)); for (int i = 0; i < N; ++i) { fprintf(fin, "%d ", rand() % 1000000); } } fclose(fin); } void PrintTopK(const char* filename, int K) { assert(filename); FILE* fout = fopen(filename, "r"); if (fout == NULL) { perror("fopen fail"); return; } int* maxHeap = (int*)malloc(sizeof(int) * K); if (maxHeap == NULL) { perror("malloc fail"); return; } //先读K个数 for (int i = 0; i < K; ++i) { fscanf(fout, "%d", &maxHeap[i]); } for (int j = (K - 2) / 2; j >= 0; --j) { AdjustDown(maxHeap, K, j); } int val = 0; while (fscanf(fout, "%d", &val) != EOF) { if (val > maxHeap[0]) { maxHeap[0] = val; AdjustDown(maxHeap, K, 0); } } for (int i = 0; i < K; ++i) { printf("%d ", maxHeap[i]); } free(maxHeap); fclose(fout); } int main() { const char* filename = "Data.txt"; int N = 100000; int K = 10; //CreateDataFile(filename, N); PrintTopK(filename, K); return 0; }
