我们本期来讲解堆结构
目录
堆的结构
堆的初始化
堆的销毁
堆的插入
向上调整算法
堆的删除
向下调整算法
取堆顶元素
判断堆是否为空
堆中元素个数
堆排序
向下调整与向上调整效率计算
Top-K问题
全部代码
堆的结构
堆是一种用数组模拟二叉树的结构
逻辑结构是我们想象出来的，物理结构是实实在在存在的
因为是用数组来实现的，所以我们访问时访问的是下标，那怎么通过下标来对应关系呢？
孩子和父节点的关系为：parent=(child-1)/2，leftchild=parent*2+1，rightchild=parent*2+2
这样我们就可以将节点之间的关系对应起来了
数组存储只适合存储完全二叉树，如果不是完全二叉树，就会出现很多空的地方，会有很大的空间浪费
我们主要掌握两种结构，一种是小堆，一种是大堆， 小堆是所有的父亲都小于等于孩子，大堆是所有父亲大于等于孩子
接着我们就来实现堆
在写堆之前，我们先来想一下，如果我们要在堆中插入数据该怎么办？
因为我是用数组实现，所以在插入时是需要考虑扩容的
插入之后还要保证大堆还是大堆，小堆还是小堆
我们再次插入一个60的话，就需要和他的祖先进行交换了，我们通过下标计算出60的父亲是25，然后交换60和25，接着再次重复进行上面的步骤，交换60和56，这次才又变成了大堆
上面这个过程我们叫做向上调整，向上调整最多调整高度次
继续回到我们的堆来，我们来写堆的结构
typedef int HPDataType;
typedef struct Heap{
HPDataType* a;
int size;
int capacity;
}HP;使用size来记录当前存储元素数量，capacity记录容量
堆的初始化
void HeapInit(HP* php) {
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
if (php->a == NULL) {
perror("malloc fail");
return;
}
php->size = 0;
php->capacity = 4;
}
我们传的是结构体的指针，所以一定不能为空，需要进行断言，接着我们给堆的数组开辟空间，初始大小根据需要来定，开辟是否成功我们判断一下，接着就是初始化其他元素了
堆的销毁
void HeapDestroy(HP* php) {
assert(php);
free(php->a);
php->size = 0;
php->capacity = 0;
free(php);
}释放数组和空间即可
堆的插入
void HeapPush(HP* php, HPDataType x) {
assert(php);
if (php->size == php->capacity) {
HPDataType* tmp = realloc(php->a,sizeof(HPDataType) * php->capacity * 2);
if (tmp == NULL) {
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}在插入前，我们要先判断是否需要扩容，接着插入并++size即可，但是我们上面说了，在插入后，要保证堆还是堆，我们需要向上调整，所以我们这里写出向上调整算法
向上调整算法
void Swap(int* x, int* y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
void AdjustUp(HPDataType* a,int child) {
int parent = (child - 1) / 2;
while (child > 0) {
if (a[child] > a[parent]) {
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}我们根据上面讲的例子就可以明白，这是一个循环，我们先找到父节点，接着进入循环，循环结束条件为child=0，即插入的元素走到堆顶，循环里我们对孩子和父亲进行比较，若父亲比孩子小，我们交换二者，接着让下标移动，否则退出循环
有了插入，我们对我们的堆进行一下测试
我们通过调试来看堆里的数据，发现为6，4，5，3，1，2，这就是我们的大堆，没有问题
堆的删除
堆的删除是删除堆里的一个元素，在写删除之前，我们仔细想想，我们是删除堆的哪里呢？
是头还是尾？删尾非常轻松，但是删尾没有意义，所以，堆的删除，是删除头，也叫删除堆顶
堆顶是一个堆里最大（最小）的数据，在实际中，无论是堆排序，还是topK，都是选大小，所以我们需要选出最值
那我们删除堆顶后，应该怎么办呢？举个例子，【40，10，15，1，2，3】这是一个堆，当我们把40删除后，我们是要把后续的数据向前挪动一位吗？答案是错误的
挪动删除有两大问题：1.效率低下，2.父子兄弟关系全乱了
原来10和15是兄弟，现在10变成了15的父亲，而且此时还不是大堆
我们要将堆顶的元素和堆中最后一个元素交换位置
交换到末尾后，删除就简单了，而且我们此时再单看左子树和右子树，也都符合我们的要求，都是大堆，只有堆顶不满足，此时就需要一个向下调整算法
void HeapPop(HP* php) {
assert(php);
assert(!HeapEmpty(php));
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a,php->size,0);
}我们先看删除函数，我们交换堆顶与堆最后一个元素的位置，使size-1即可，接着就是向下调整
向下调整算法
void AdjustDown(HPDataType* a,int n, int parent) {
int child = parent * 2 + 1;
while (child < n) {
if (child+1<n && a[child] < a[child + 1]) {
child++;
}
if (a[child] > a[parent]) {
Swap(&a[child], &a[parent]);
parent=child;
child = parent * 2 + 1;
}
else {
break;
}
}
}与向上调整类似，也是一个循环，只不过这次我们是从头开始调整的，所以需要多一个参数来接收数组大小，向下调整是将堆顶这个小的数据放在他应该出现的位置，但和向上调整不同，父节点有两个孩子，我们选择和较大的孩子进行交换，不然可能会出现一些别的情况，我们先假设左孩子大，然后进行比较，如果这个节点有右孩子，并且右孩子更大，那么就将child更新，然后我们对父亲和孩子进行比较，如果孩子比父亲大，就交换，否则退出循环
向上调整和向下调整都是有前提的，向下调整的前提是左右子树都是大堆/小堆，向上调整的前提是除了child位置，前面的数据构成堆
取堆顶元素
HPDataType HeapTop(HP* php) {
assert(php);
return php->a[0];
}判断堆是否为空
bool HeapEmpty(HP* php) {
assert(php);
return php->size == 0;
}堆中元素个数
int HeapSize(HP* php) {
assert(php);
return php->size;
}
这三个函数都非常简单
有了这些函数，我们来对堆进行一下测试
堆排序
有了上面的知识，我们接着来学习堆排序，刚才的操作，只能叫做有序打印，而不是排序，现在才是真正的排序
堆排序并不是我们写一个堆，将数据全部放入堆里，然后再取堆顶，这样做的话效率太低，我们还要写一个堆出来
我们看我们的数组，虽然有了数据，但这些数据并不能构成堆，所以我们需要建堆
我们需要用向上调整来建堆，就是模拟插入的过程，即我们先把数组第一个元素看作堆里的元素，接着把第二个元素看作堆的元素插入，然后向上调整，接着是第三个元素，以此类推
这种建堆的时间复杂度为O(N*logN)，此时我们的堆就建好了
通过调试我们可以看到
接着，我们要排升序的话，要建大堆还是小堆呢？
很大人可能会认为排升序要建小堆，但是建小堆就出问题了，小堆的话，第一个数排好了，剩下的数怎么办呢？就又变成了我们上面的挪动删除那样了
所以我们需要建大堆，我们将最大的数和最后一个元素交换位置，接着，我们不管最后一个数，将前面的数看作堆，然后向下调整，最多调整高度次就可以选出次大的数，时间复杂度为O(logN)
堆排序的时间复杂度为O(N*logN)
void HeapSort(int* a,int n) {
//建堆，向上调整
for (int i = 1; i < n; i++) {
AdjustUp(a, i);
}
int end = n - 1;
while (end>0) {
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}堆排序写起来是很简单的，前提是有我们的向上调整和向下调整
排降序的话建小堆即可
我们的建堆还有一种办法，是使用向下调整建堆，这种更常用，我们要从倒数第一个非叶子节点开始调整，因为调整叶子节点没意义
我们从6这个节点开始向下调整，6是尾节点的父亲，我们可以通过计算得到，调整完6后，我们要调整7， 6往前走一步就到了7，我们找到7这个节点左右孩子大的那个，就是9，然后交换9和7接着调整5，交换8和5，以此类推，最终9到达了堆顶
向下调整的效率是比向上调整高的，并且我们只需要写一个向下调整，不需要写向上调整就可以完成堆排序
n-1是最后一个数的下标，再-1除以2是求父亲节点
接着我们来对比向上调整和向下调整的效率
向下调整与向上调整效率计算
向上调整建队的时间复杂度为O(N*longN)，向下调整为O(N)
下面我们进行证明
我们向下调整，是从倒数第二层开始调整，假设高度为h，倒数第二层节点数为2^(h-2)
我们用T(N)表示建堆的总次数
倒数第二层最坏需要调整1次，举个例子
我们的这个堆里，倒数第二层里的7需要和最后一层的9进行交换，所以是调整1次，在最坏的情况下，倒数第二层的所有节点都需要和他的孩子进行交换
所以倒数第二层的总调整次数为2^(h-2)*1
倒数第三层总调整次数为2^(h-3)*2
......
第二层总调整次数为2^1*(h-2)
第一层需要调整2^0*(h-1)
T(N)=2^(h-2)*1+2^(h-3)*2+......+2^1*(h-2)+2^0*(h-1)
这是一个等差乘以等比，我们要用错位相减法来计算
两边同时乘以2后变成：2*T(N)=2^(h-1)*1+2^(h-2)*2+......+2^2*(h-2)+2^1*(h-1)
接着我们进行相减，得到：T(N)=2^(h-1) + 2^(h-2)+2^(h-3)+...+ 2^2+2^1 - 2^0*(h-1)
最后的 - 2^0*(h-1)，我们化解为 -(2^0-h)，原理为2^0是1，我们不写，就变成了h-1，1又可以写成2^0
此时T(N)=2^(h-1) + 2^(h-2)+2^(h-3)+...+ 2^2+2^1+2^0 -h
前面的是是等比数列，计算结果为2^h-1，所以T(N)=2^h-1-h
如果这棵数有N个节点，那么2^h-1=N，N也就是数组大小，所以T(N)的前面是N，h是longN
所以向下调整的时间复杂度为O(N-longN），longN可以忽略不记，所以时间复杂度为O(N)
分开看就是每一层的节点数乘以向下调整多少次，然后加起来
接着我们看向上调整建堆
T(N)=2^1*1 + 2^2*2 + ... + 2^(h-2)*(h-2) + 2^(h-1)*(h-1)
我们分析一下，2^1*1代表第2层节点数乘以调整次数1次，第二层有两个节点，我们是模拟插入，即先插入一个，这个节点有可能和第一层的节点进行交换，接着插入第二个，第二个节点也可能和第一层的节点交换，交换次数最多为1，其他的以此类推
接着我们再用错位相减法计算
2*T(N)=2^2*1 + 2^3*2 + ... +2^(h-2)*(h-3) + 2^(h-1)*(h-2) + 2^(h)*(h-1)
相减得到T(N)= -2^1 - 2^2 -2^3 - ...... -2^(h-2) - 2^(h-1) +2^(h)*(h-1)
2^(h)*(h-1)分解变为 -2^h + 2^h*h，不分解也可以
最终得到T(N)= - 2^h+2 + 2^h*h - 2^h
又N=2^h-1，T(N)最后左边是N ，中间是N*longN，右边也是N，即时间复杂度为O((longN-2)*N)
也就是N*longN
所以向上调整的效率是比向下调整的效率要低的，综上，我们的堆排序用向下调整就行
Top-K问题
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素
我们要找出N个数里最大的前K个，我们可以建N个大堆，然后pop k次就行
那假设N很大呢？比如N为100亿
此时数据在内存存不下，数据是在磁盘文件里的，要解决这个问题，就有人想出了这样的一个方法
我们前k个数据建小堆，遍历剩下的数据，如果这个数据比堆顶数据要大，就替代他进堆，向下调整，最后这个小堆的数据就是最大的前k个
这个思想是不是非常巧妙？最大的前k个来了一定比堆顶大，就可以进堆，如果我们建大堆的话，就有可能有一个很大的数在堆顶，其他数就进不了堆了
void PrintTopK(const char* file, int k) {
//1.用前k个元素建小堆
int* topk = (int*)malloc(sizeof(int) * k);
if (topk == NULL) {
perror("malloc fail");
return;
}
FILE* fout = fopen(file, "r");
if (fout == NULL) {
perror("fopen error");
return;
}
//读前k个数据建堆
for(int i=0;i<k;i++)
{
fscanf(fout, "%d", &topk[i]);
}
for (int i = (k - 1-1)/2; i >=0; i--) {
AdjustDown(topk, k, i);
}
//2.将剩下的n-k个元素依次与堆顶元素比较，满足条件进行替换
int val = 0;
int ret= fscanf(fout, "%d", &topk[i]);
while (ret != EOF) {
if (val > topk[0]) {
topk[0] = val;
AdjustDown(topk, k, 0);
}
ret = fscanf(fout, "%d", &val);
}
//打印数据
for (int i = 0; i < k; i++) {
printf("%d ", topk[i]);
}
printf("\n");
free(topk);
fclose(fout);
}假设数据在文件里，所以我们使用文件的方式来写这个函数，最后的打印数据大家根据需求来修改即可
以上即为本期全部内容，希望大家可以有所收获
最后附上全部代码
全部代码
//heap.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap{
HPDataType* a;
int size;
int capacity;
}HP;
void HeapInit(HP* php);
void HeapPush(HP* php,HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
void HeapDestroy(HP* php);//heap.c
#include"heap.h"
void HeapInit(HP* php) {
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
if (php->a == NULL) {
perror("malloc fail");
return;
}
php->size = 0;
php->capacity = 4;
}
void Swap(int* x, int* y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
void AdjustUp(HPDataType* a,int child) {
int parent = (child - 1) / 2;
while (child > 0) {
if (a[child] > a[parent]) {
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
void HeapPush(HP* php, HPDataType x) {
assert(php);
if (php->size == php->capacity) {
HPDataType* tmp = realloc(php->a,sizeof(HPDataType) * php->capacity * 2);
if (tmp == NULL) {
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
void AdjustDown(HPDataType* a,int n, int parent) {
int child = parent * 2 + 1;
while (child < n) {
if (child+1<n && a[child] < a[child + 1]) {
child++;
}
if (a[child] > a[parent]) {
Swap(&a[child], &a[parent]);
parent=child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
void HeapPop(HP* php) {
assert(php);
assert(!HeapEmpty(php));
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a,php->size,0);
}
HPDataType HeapTop(HP* php) {
assert(php);
return php->a[0];
}
bool HeapEmpty(HP* php) {
assert(php);
return php->size == 0;
}
int HeapSize(HP* php) {
assert(php);
return php->size;
}
void HeapDestroy(HP* php) {
assert(php);
free(php->a);
php->size = 0;
php->capacity = 0;
free(php);
}//test.c
#include"heap.h"
void AdjustUp(HPDataType* a, int child);
void Swap(int* x, int* y);
void AdjustDown(HPDataType* a, int n, int parent);
void test1() {
HP hp;
HeapInit(&hp);
HeapPush(&hp, 1);
HeapPush(&hp, 2);
HeapPush(&hp, 3);
HeapPush(&hp, 4);
HeapPush(&hp, 5);
HeapPush(&hp, 6);
while (!HeapEmpty(&hp)) {
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
}
void HeapSort(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>0) {
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
void PrintTopK(const char* file, int k) {
//1.用前k个元素建小堆
int* topk = (int*)malloc(sizeof(int) * k);
if (topk == NULL) {
perror("malloc fail");
return;
}
FILE* fout = fopen(file, "r");
if (fout == NULL) {
perror("fopen error");
return;
}
//读前k个数据建堆
for(int i=0;i<k;i++)
{
fscanf(fout, "%d", &topk[i]);
}
for (int i = (k - 1-1)/2; i >=0; i--) {
AdjustDown(topk, k, i);
}
//2.将剩下的n-k个元素依次与堆顶元素比较，满足条件进行替换
int val = 0;
int ret= fscanf(fout, "%d", &topk[i]);
while (ret != EOF) {
if (val > topk[0]) {
topk[0] = val;
AdjustDown(topk, k, 0);
}
ret = fscanf(fout, "%d", &val);
}
//打印数据
for (int i = 0; i < k; i++) {
printf("%d ", topk[i]);
}
printf("\n");
free(topk);
fclose(fout);
}
void test2() {
int a[10] = { 2,1,5,7,6,8,0,9,4,3 };
HeapSort(a, 10);
for (int i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
}
int main() {
test2();
return 0;
}如有错误，还请指正
