文章目录
- 一、堆
- 1. 概念与分类
- 2. 结构与性质
- 3. 入堆
- 4. 出堆
- 二、堆排序
- 三、堆排序的应用——TOP-K问题
一、堆
1. 概念与分类
上一期我们提到，二叉树的实现既可以用顺序结构，也可以用链式结构。本篇我们来学习顺序结构的二叉树，起个新名字——堆（heap）。
堆是完全二叉树，它的底层是顺序结构的数组，具有二叉树特性的同时，还有一些其他性质：
堆分为大堆和小堆（或称为大根堆、小根堆）：
- 大堆：大堆的每个结点的存储值都 >= 它的子结点的存储值。
- 小堆：小堆的每个结点的存储值都 <= 它的子结点的存储值。
譬如，在一个大堆中，某一个父结点的值为20，则它的子结点的值一定<=20；在一个小堆中，某一个父结点的值为20，则它的子结点的值一定>=20。
左孩子和右孩子的值的大小关系不确定。
换句话说，一个堆一定是大堆或小堆。以下的二叉树，既不是大堆也不是小堆，它们就不是堆：
2. 结构与性质
定义数据结构堆：
typedef struct Heap
{
HPDataType* arr;
int size;
int capacity;
}HP;
上面的画图是用逻辑结构表示堆，用存储结构表示堆就要用到数组了，牢记二叉树结点的编号方式：从上到下，从左到右：
不难推断，堆的数组中有下列性质：
- 大堆的首元素（根结点）是整个堆的最大值，小堆的首元素（根结点）是整个堆的最小值。
- 若子结点的下标为i，则它的父结点是(i-1)/2。
- 若父结点的下标为i，则它的左孩子是2i+1，右孩子是2i+2。结点个数是n，2i+1 >= n 说明无左孩子，2i+2 >= n 说明无右孩子。
顺带给出堆的初始化和销毁方法，以及后面要用到的交换两个变量值的方法：
void HPInit(HP* php)
{
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}
void HPDestory(HP* php)
{
assert(php);
if (php->arr != NULL)
free(php->arr);
php->arr = NULL;
php->size = php->capacity = 0;
}
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}
3. 入堆
想要把一个新的数据插入堆，分为两步：
- 把它插入堆数组末尾
- 仅仅插入数据后，可能会破坏堆的性质，所以还要进行“向上调整”操作：将新插入结点顺着其双亲往上调整位置至满足大堆或小堆的位置。
我们以下面一个小堆为例，插入一个新数据10，如果它小于其父结点（不符合小堆），两者交换。再和新父结点比较，如果小于交换……直到满足小堆：
所以，我们要知道向上调整算法：它有两个参数：要被调整的堆数组，要调整位置的结点的下标：
void AdjustUp(HPDataType* arr, int child)
{
int parent = (child - 1) / 2; //找这个结点的父结点
while (child > 0)
{
//调整的是小堆: <
//调整的是大堆: >
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
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 ? 5 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("relloc fail!");
exit(1);
}
php->arr = tmp;
php->capacity = newcapacity;
}
php->arr[php->size] = x; //新数据插到末尾，即下标为size的位置
AdjustUp(php->arr, php->size);
php->size++;
}
测试：
我们来实现一个小堆，乱序给一些数：
将打印结果排列成堆的逻辑结构看看，发现确实是正确的小堆：
4. 出堆
我们所谓的出堆，出的并不是数组末尾数据，出的是第一个数据——堆的根结点。但是，直接除去数组首元素，再将后面元素的下标全体前挪，会使堆的所有结点位置关系“大乱套”，再想调整可就麻烦了。
因此，我们选择这样的出堆定元素方法：先将堆顶数据和堆的最后一个数据交换，size- -把数组末尾数据出掉，再对堆顶元素进行“向下调整”操作。相比刚才所有结点位置大乱套，这样只要调整一个结点的位置就好了。
向下调整算法和向上调整类似：它是比较结点和其较大或较小孩子的值，不断往下交换调整位置直至满足大堆或小堆：
向下调整算法有三个参数：要被调整的堆数组、要调整的结点的下标、堆的数据个数
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = 2 * parent + 1;
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 = 2 * parent + 1;
}
else //调整完成
{
break;
}
}
}
这样，我们就能实现出堆操作了：
void HPPop(HP* php)
{
assert(php);
assert(php->size != 0); //堆不能为空，否则无数据可出
Swap(&php->arr[0], &php->arr[php->size - 1]); //交换堆顶和堆尾数据
php->size--; //将堆尾数据出掉
AdjustDown(php->arr, 0, php->size);
}
测试：
我们来实现一个大堆，乱序给一些数，再进行一次出堆：
分析逻辑结构，可以看到大堆实现成功，出堆也没有问题：
二、堆排序
堆排序是一种排序方法，不是借助堆的数据结构，而是利用堆的思想进行排序：
一个n个元素的数组，假如想排升序，就将数组建成一个大堆，堆顶是最大值，将堆顶和堆尾交换，下标n-1处就是最大值了；我们再把前n-1个数据调整成大堆，此时堆顶就是第二大的数据，堆顶和堆尾交换，下标n-2处就是第二大值了……直至排序完成。
相反地，想排成降序就建小堆，道理是一样的，我们下面就以建成大堆为例。
堆排序的关键在于一开始建堆的方法，可以分为向下调整建堆和向上调整建堆：
void HPCreat_Down(int* arr, int n) //向下调整算法建堆
{
//从尾结点的父结点开始往上遍历，每一个结点都进行向下调整
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, i, n);
}
}
void HPCreat_Up(int* arr, int n) //向上调整算法建堆
{
//从第一个结点开始往下遍历，每一个结点都进行向上调整
for (int i = 0; i < n; i++)
{
AdjustUp(arr, i);
}
}
//注：建的是大堆还是小堆，取决于AdjustUp和AdjustDown函数中的大于还是小于号，上面提到过
知道了建堆方式后，就能实现堆排序了：
void HeapSort(int* arr, int n)
{
HPCreat_Down(arr, n);
//或HPCreat_Up(arr, n);
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end); //对新堆顶进行向下调整，以保证堆的性质
end--;
}
}
测试：
很顺利。
关于两种建堆方式的时间复杂度：
推导需要用到数列相关定理公式，我就不再证明了，可以直接记住结果：
- 向下调整建堆：T(n) = n - log2(n+1)，O(n)
- 向上调整建堆：T(n) = (n+1) [log2(n+1) - 2] + 2，O(n*logn)
可见，向下调整建堆算法更好一些。
三、堆排序的应用——TOP-K问题
TOP-K问题，即求n个数据中前K个最大值或最小值，一般情况下n都很大且n >> k。
我们能想到的最简单的方法就是排序了，但是如果数据量太大，数据不能一下子全部加载到内存中，排序就不可取了。最佳的方式就是用堆来解决，思路为：
- 取前k个数据建堆，遍历剩下的n-k个数据跟堆顶比较。
- 如果找的是前k个最大值，就建小堆。若第k+1个数比堆顶大，就用它替换堆顶，再调整堆，再比较第k+2个数和堆顶……遍历完，最后堆中的k个数就是n个数里面前的k个最大值了。
- 如果找的是前k个最小值，就建大堆。若第k+1个数比堆顶小，就用它替换堆顶，再调整堆，再比较第k+2个数和堆顶……遍历完，最后堆中的k个数就是n个数里面前的k个最小值了。
应该很好理解吧。
举个栗子，我先来造十万个数据，保存到一个文本文件data.txt中
void CreatData()
{
srand(time(0));
FILE* file = fopen("data.txt", "w");
if (file == NULL)
{
perror("fopen fail!");
exit(2);
}
for (int i = 0; i < 100000; i++)
{
int x = (rand() + i) % 100000 + 1;
fprintf(file, "%d\n", x);
}
fclose(file);
}
最后来实现TOP_K算法（以找前k个最小值为例）：
void Top_K()
{
int k;
printf("请输入K:");
scanf("%d", &k);
FILE* file = fopen("data.txt", "r");
if (file == NULL)
{
perror("fopen fail!");
exit(2);
}
int* maxHeap = (int*)malloc(sizeof(int) * k);
if (maxHeap == NULL)
{
perror("malloc fail!");
exit(1);
}
for (int i = 0; i < k; i++)
{
//先将前k个数存到maxHeap中
fscanf(file, "%d", &maxHeap[i]);
}
HPCreat_Down(maxHeap, k); //找前k个最小值，建大堆
//遍历剩下的数
int x;
while (fscanf(file, "%d", &x) != EOF) //fscanf文件读取结束会返回EOF
{
//谁小谁当堆顶
if (x < maxHeap[0])
{
maxHeap[0] = x;
AdjustDown(maxHeap, 0, k);
}
}
fclose(file);
//处理完成，打印结果
for (int i = 0; i < k; i++)
{
printf("%d ", maxHeap[i]);
}
}
测试：
可以看到，每次输入一个k，都能找到前k个最小值，只不过不是按大小顺序输出的。顺带一提，这个算法的时间复杂度O(n) = k + (n - k)log2k
本篇完，感谢阅读
