一、堆的概念及结构
1.1堆的概念
1.2堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
1.3堆的结构
二、堆的实现
2.1堆向下调整算法（父亲与孩子做比较）
我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
以下面图片为例：建小堆过程中父亲不断与较小的孩子交换
用代码来实现：
void AdjustDown(HPDataType* a, int n, int parent)//n是参与向下算法的元素的个数 { int child = parent * 2 + 1; while (child < n) { //建小堆，找到两个孩子中较小的那一个 if (child + 1 < n && a[child + 1] < a[child]) { child++; } //如果父亲不比孩子大，就证明已经是小堆了，直接跳出循环； //如果比孩子大就一直交换 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else break; } }
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 = (child - 1) / 2; } else break; } }
2.3堆的创建（向下建堆）
我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的 子树开始调整（向下调整），一直调整到根节点的树，就可以调整成堆。
假定有数组 int a [] = { 1 , 5 , 3 , 8 , 7 , 6 };
2.4向下建堆的时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 ( 时间复杂度本来看的就是近似值，多几个节点不影响最终结果 ) ：
因此：向下建堆的时间复杂度为O(N)。
既然谈到了向下建堆的时间复杂度，不妨就算一下向上建堆的时间复杂度：
冲两张图中可以看到：向下调整建堆的效率略高于向上调整建堆的效率，所以我上面所讨论的也都是向下调整建堆的实现方法。
2.5堆的插入
先插入一个 10 到数组的尾上，再进行向上调整算法，直到满足堆。
代码实现：
void HeapPush(Heap* hp, HPDataType x) { assert(hp); //判满以及扩容 if (hp->_capacity == hp->_size) { int newCapacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity; 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); }
2.6堆的删除
删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
代码实现：
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); }
2.7堆的完整代码实现
//Heap.h #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> typedef int HPDataType; typedef struct Heap { HPDataType* _a; int _size; int _capacity; }Heap; //堆的初始化 void HeapInit(Heap* hp); // 堆的构建 void HeapCreate(Heap* hp, HPDataType* a, int n); //交换 void Swap(HPDataType* a, HPDataType* b); //向上调整 void AdjustUp(HPDataType* a, int child); //向下调整 void AdjustDown(HPDataType* a, int n, int parent); //打印 void HeapPrint(Heap* hp); // 堆的销毁 void HeapDestory(Heap* hp); // 堆的插入 void HeapPush(Heap* hp, HPDataType x); // 堆的删除 void HeapPop(Heap* hp); // 取堆顶的数据 HPDataType HeapTop(Heap* hp); // 堆的数据个数 int HeapSize(Heap* hp); // 堆的判空 int HeapEmpty(Heap* hp);
//Heap.c #include "Heap.h" void HeapInit(Heap* hp) { assert(hp); hp->_a = NULL; hp->_capacity = 0; hp->_size = 0; } 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 = n; hp->_size = n; memcpy(hp->_a, a, sizeof(HPDataType) * n); for (int i = 1; i < n; i++) { AdjustUp(hp->_a, i); } } void Swap(HPDataType* a, HPDataType* b) { HPDataType tmp = *a; *a = *b; *b = tmp; } 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 = (child - 1) / 2; } else break; } } void AdjustDown(HPDataType* a, int n, int parent)//n是参与向下算法的元素的个数 { int child = parent * 2 + 1; while (child < n) { //建小堆，找到两个孩子中较小的那一个 if (child + 1 < n && a[child + 1] < a[child]) { child++; } //如果父亲不比孩子大，就证明已经是小堆了，直接跳出循环； //如果比孩子大就一直交换 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else break; } } void HeapDestory(Heap* hp) { assert(hp); free(hp->_a); hp->_capacity = 0; hp->_size = 0; } void HeapPush(Heap* hp, HPDataType x) { assert(hp); //判满以及扩容 if (hp->_capacity == hp->_size) { int newCapacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity; 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 HeapPrint(Heap* hp) { assert(hp); for (int i = 0; i < hp->_size; i++) { printf("%d ", hp->_a[i]); } printf("\n"); } 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->_size > 0); return hp->_a[0]; } int HeapSize(Heap* hp) { return hp->_size; } int HeapEmpty(Heap* hp) { assert(hp); if (hp->_size == 0) return 0; else return 1; }
三、堆的应用
3.1堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
1. 建堆：
升序：建大堆，降序：建小堆。
2. 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
具体实现代码如下：
void HeapSort1(int* a, int n) { //向上调整建堆 /*for (int i = 1; i < n; i++) { AdjustUp(a, i); }*/ //向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--)//从第一个非叶子节点开始向下调整 { AdjustDown(a, n, i); } //排序 int end = n - 1; while (end) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } }
3.2TOP-K问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中 ) 。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前 K 个元素来建堆 :
前 k 个最大的元素，则建小堆，前 k 个最小的元素，则建大堆 。
2. 用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余 N-K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。
具体实现代码如下：
void CreatNData() { // 造数据 int n = 10000000; srand(time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return; } //将数据写入data文件中 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) { FILE* fout = fopen(filename, "r"); if (fout == NULL) { perror("fopen fail"); exit(-1); } 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]); } for (int i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(minHeap, k, i); } //将剩余的n-k各元素与堆顶的元素进行交换 int x = 0; while (fscanf(fout, "%d", &x) != EOF) { if (x > minHeap[0]) { minHeap[0] = x; AdjustDown(minHeap, k, 0); } } //排序 int end = k - 1; while (end) { Swap(&minHeap[0], &minHeap[end]); AdjustDown(minHeap, end, 0); end--; } for (int i = 0; i < k; i++) { printf("%d ", minHeap[i]); } free(minHeap); fclose(fout); }
