堆的应用
前言
堆的实现
本篇仍然是建小堆来示范
代码位置
堆的特性决定了它的应用，我们可以用堆来对数据进行排序，即堆排序。
既然涉及到排序，我们需要关注的主要一点就是它的时间复杂度，所以我们先计算建堆需要的两种算法的时间复杂度。
向上调整算法建堆时间复杂度
- 先上代码
void AdjustUp(HPDataType* arr,int child) { int parent = (child - 1) / 2; while (child > 0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换 { if (arr[child] < arr[parent]) { Swap(&arr[parent], &arr[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } void HPPush(HP* php, HPDataType x) { assert(php); //判断空间是否足够 if (php->size == php->capacity) { //扩容 int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity; HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } php->arr = tmp; php->capacity = newCapacity; } php->arr[php->size] = x; AdjustUp(php->arr, php->size); ++php->size; }
注意：这是一次插入数据
计算向上调整算法建堆时间复杂度
- 因为堆是完全⼆叉树，⽽满⼆叉树也是完全⼆叉树，此处为了简化使⽤满⼆叉树来证明(时间复杂度本来看的就是近似值，多⼏个结点不影响最终结果)
- 所以我们假设此次建堆中有n个数据，最后建成了一个高度为h的堆
- 我们可以发现：
- 当根节点为第一层时，我们在第k(1=
所以以最坏情况计算时间复杂度
分析：
- 第1层，20个结点，需要向上移动0层
- 第2层，21 个结点，需要向上移动1层
- 第3层，22 个结点，需要向上移动2层
- 第4层，23 个结点，需要向上移动3层
- …
- 第h层，2h-1 个结点，需要向上移动h-1层
计算过程如下：
为等比数列乘以等差数列，使用错位相减法就行啦
由此可得：
向上调整算法建堆时间复杂度为：O(n ∗ log2n)
即为nlogn
向下调整算法建堆时间复杂度
- 先上代码
void AdjustDown(HPDataType* arr, int parent, int n) { int child = parent * 2 + 1;//左孩子 //while (parent < n) while (child < n) { //找左右孩子中找最小的 if (child + 1 < n && arr[child] > arr[child + 1]) { child++; } if (arr[child] < arr[parent]) { Swap(&arr[child], &arr[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }
在堆的实现方法中我们讲到堆的向下调整算法是在删除堆顶数据时使用的
这是基于堆顶数据以下的左右子树都是堆才是才能调整的
而当我们拿到一组乱序的数据，个数为n，显然是不能从堆顶开始向下调整的
怎么办，那就换思路：
既然向下调整算法需要左右子树都为堆，那我们从最后一棵子树开始调整不就可以了吗
如下图：这里我们还是用满二叉树推导，最后一颗子树的根节点即（n-1-1）/2,我们就从这一棵子树的根节点开始调整
所以第k(1=
分析：
- 第1层，20个结点，需要向下移动h-1层
- 第2层，21个结点，需要向下移动h-2层
- 第3层，22个结点，需要向下移动h-3层
- 第4层，23个结点，需要向下移动h-4层
- …
- 第h-1层，2h-2个结点，需要向下移动1层
同样也是等比数列乘以等差数列形式，使用错位相减法
由此可得：向下调整算法建堆时间复杂度为：O(n)
堆排序
方案一
- 前篇：堆的实现方法，在上篇博客中我们实现了堆，那就可以借助已有的数据结构堆，将数组中元素一个一个插入堆，然后依次取堆顶元素再出堆
// 1、需要堆的数据结构 // 2、空间复杂度 O(N) void HeapSort1(int* a, int n) { HP hp; int arr1[6] = { 34,29,48,23,10,50 }; for(int i = 0; i < 6; i++) { HPPush(&hp,a[i]); } int i = 0; while (!HPEmpty(&hp)) { a[i++] = HPTop(&hp); HPPop(&hp); } HPDestroy(&hp); }
- 实际操作中太过麻烦，要求很多，所以一般不会这样做
方案二
- 向上调整算法数组直接建堆
- 建好堆后，将堆顶元素与最后一个元素交换（若建小堆的则每次取的都是最小的，所以为降序）
- 然后将交换过去的堆顶元素进行向下调整
- 重复上述步骤
void HeapSort2(int* arr, int n) { int i = 0; for ( i = 0; i < n; i++) { HPAdjustUp(arr, i); } int end = n - 1; while (end) { Swap(&arr[0],&arr[end]); HPAdjustDown(arr, 0, end); end--; } }
- 时间复杂度
- 两部分：
- 建堆：O(nlogn)
- 逐个交换然后向下调整，外层循环（n-1）次，内层每一次向下调整最多log2(n+1)层，时间复杂度O(nlog(n))
- 总共为O(nlogn+nlogn)
所以此种堆排序为O(nlogn)
方案三
将方案二建堆算法替换为向下调整算法即可
void HeapSort3(int* arr, int n) { for (int i =(n-1-1)/2 ; i >= 0; i--) { HPAdjustDown(arr, i, n); } int end = n - 1; while (end) { Swap(&arr[0], &arr[end]); HPAdjustDown(arr, 0, end); end--; } }
计算同理，但建堆为O(n)，总共为O(n+nlogn)，也是O(nlogn)
总结
- 由于建堆使用向下调整算法更快速，所以堆排序使用方案三为最佳
- 要排升序，建大堆->每次取最大的到最后一位
- 要排降序，建小堆->每次取最小的到最后一位
Top-k问题
TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。
⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题，能想到的最简单直接的⽅式就是排序，但是：如果数据量⾮常⼤，排序就不太可取了 (可能数据都不能⼀下⼦全部加载到内存中)。
最佳的⽅式就是⽤堆来解决，基本思路如下：
- ⽤数据集合中前k个元素来建堆
- 前k个最⼤的元素，则建⼩堆；前k个最⼩的元素，则建⼤堆
- ⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素 ，然后再将交换进去后的元素向下调整（保证这k个元素始终是堆），最后将剩余N-k个元素依次与堆顶元素⽐完之后，堆中剩余的K个元素就是所求的前k个最⼩或者最⼤的元素
代码如下:
- 为了检验是否写的正确，所以先造数据
void CreateNDate() { // 造数据 int n = 100000; 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) % 1000000; fprintf(fin, "%d\n", x); } fclose(fin); } void TOPk() { int k = 0; printf("请输入k:"); scanf("%d", &k); const char* file = "data.txt"; FILE* fout = fopen(file, "r"); if (fout == NULL) { perror("fopen fail!"); exit(1); } int* minHeap = (int*)malloc(k * sizeof(int)); if (minHeap == NULL) { perror("malloc fail!"); exit(2); } //从文件中读取前K个数据 for (int i = 0; i < k; i++) { fscanf(fout, "%d", &minHeap[i]); } //建堆---小堆 for (int i = (k - 1 - 1) / 2; i >= 0; i--) { HPAdjustDown(minHeap, i, k); } int x = 0; while (fscanf(fout, "%d", &x) != EOF) { //读取到的数据跟堆顶的数据进行比较 //比堆顶值大，交换入堆 if (x > minHeap[0]) { minHeap[0] = x; HPAdjustDown(minHeap, 0, k); } } for (int i = 0; i < k; i++) { printf("%d ", minHeap[i]); } fclose(fout); } int main() { //CreateNDate(); TOPk(); return 0; }
