堆及其多种接口与堆排序的实现

我们本期来讲解堆结构

目录

堆的结构

堆的初始化

堆的销毁

堆的插入

向上调整算法

堆的删除 

向下调整算法

取堆顶元素

判断堆是否为空

堆中元素个数

 堆排序

向下调整与向上调整效率计算

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;
}

如有错误，还请指正