目录
堆
经过了树的介绍，终于轮到我们的堆啦！
堆其实就是一种完全二叉树，用数组存储，不过多了一些限制条件：堆中某个节点的值总是不大于或不小于其父节点的值
总结以上就有堆的两点性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
- 当某个节点的值总是不大于父节点的值的时候，堆顶的数据往往是最小的，所以其被称为小堆
- 当某个节点的值总是不小于父节点的值的时候，堆顶的数据往往是最大的，所以其被称为大堆
注意：堆只有父子之间有大小的比较关系，而兄弟之间并没有大小的关系，所以堆并不是有序的（关键，容易和二叉查找树混淆！！！）
堆的建立(本篇以小堆为例，大堆实现方法一样）
堆的结构定义
和栈同为数组，所以这里的结构定义的方式一模一样，不过后续的操作是完全不一样的，这里就不赘述了
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}Heap;
堆的初始化
- 仍然是在插入的时候再开辟空间，此处置空指针即可
- 依然是老生常谈的问题——传进来的堆要存在，直接assert暴力断言即可，后续函数接口也仍然都要有这个操作，后续就不赘述了
- 指针置空，数据置0
void HeapInit(Heap*hp)
{
assert(hp);
hp->capacity = hp->size = 0;
hp->a = NULL;
}
堆的插入
堆的基础算法——向上调整算法
- 堆的建立应该基于其性质之上——堆中某个节点的值总是不大于或不小于其父节点的值
- 因为不能保证插入数据后堆的性质不被破坏（因为对于插入的数据的前后大小关系未知），所以在每次插入数据后，都要进行一次调整
- 因为在堆中只有父子之间有关系，兄弟之间无关系，所以只用循环地对父子之间进行调整即可，我们称其为向上调整
- 一旦父子之间符合相关关系或者孩子到达堆顶的时候，跳出循环
代码如下：
//向上调整算法
void AdjustUp(Heap* hp, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (hp->a[child] < hp->a[parent])
{
Swap(&hp->a[child], &hp->a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
插入注意事项
- 在堆末尾插入数据后，对插入的数据进行向上调整操作，以保持堆的性质不变
- 进行向上调整之前size先++，size表示数据的个数，所以我们要对数组里下标为size-1的数据进行向上调整
- 如果size==capacity，就进行扩容操作
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
//满了先扩容
if (hp->capacity == hp->size)
{
int newcapacity = hp->capacity == 0 ? 4 : (hp->capacity * 2);
HPDataType *tmp=(HPDataType*)realloc(hp->a,sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail\n");
return;
}
hp->capacity = newcapacity;
hp->a = tmp;
}
hp->a[hp->size] = x;
hp->size++;
AdjustUp(hp,hp->size-1);
}
堆的判空
- 和栈、顺序表一样，堆数据删除之前要有数据可删，所以要进行判空操作
- 将其封装成函数接口，可以提高代码的可读性
相关函数接口如下：
bool HeapEmpty(Heap* hp)
{
assert(hp);
return hp->size == 0;
}
堆的删除
堆的删除基础算法——向下调整算法
- 堆的删除应该基于其性质之上——堆中某个节点的值总是不大于或不小于其父节点的值
- 这里的删除和顺序表以及栈一样，size--即可，并不是真的抹除数据
- 如果是和数组元素头删一样，那么就不能保证堆的性质不变
- 所以我们将堆末尾数据与堆顶数据交换，然后size--就将堆顶元素删除了，然后将堆顶元素依次和孩子比较并交换（小堆选择更小的那个孩子进行交换），我们称其为向下调整算法
- 一旦其符合相关父子关系或者没有孩子的时候就跳出循环
-
//向下调整算法 void AdjustDown(Heap* hp, int n, int parent) { int child = parent * 2 + 1; while (child < n) { //从左右子树中找更小的一个孩子 if (child+1<n && hp->a[child] > hp->a[child+1]) { child++; } if (hp->a[parent] > hp->a[child]) { Swap(&hp->a[parent], &hp->a[child]); parent = child; child = parent * 2 + 1; } else { break; } } }
删除注意事项
- 删除之前先对堆进行判空，直接asser暴力断言即可
- 将堆顶元素与堆末尾数据交换后，先对size--，相当于将原来的堆顶数据抹除，再对堆顶数据进行向下调整，以保持堆的性质不变
代码如下：
// 堆的删除
void HeapPop(Heap*hp)
{
assert(hp);
assert(!HeapEmpty(&hp));
Swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;
AdjustDown(hp, hp->size, 0);
}
堆的数据个数
size即表示堆的数据个数了，所以返回size即可
// 堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->a[hp->size];
}
取堆顶的数据
判空，不为空直接返回即可
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(&hp));
return hp->a[0];
}
堆的销毁
- 和栈的销毁一样，先free掉数组，然后指针置空
- size，capacity置0
// 堆的销毁
void HeapDestory(Heap* hp)
{
assert(hp);
hp->a = NULL;
hp->capacity = hp->size = 0;
}
堆这种数据结构其实并不适合用来存储数据，而是进行一些操作，比如实现堆排序和解topk问题，
这两个问题是堆的经典应用，在学习完堆的建立后就来看看吧
堆排序
- 堆排序可谓是堆的经典应用之一，也是一种很牛的排序算法，时间复杂度为 O（N*logN），这也是学习它的原因之一
- 对数组排序，也就是对数组建堆。升序建大堆，降序建小堆，等会以降序来解释这个结论，学会了降序，升序也就是换换大于号小于号的事情。
- 首先，我们要对数组建堆。这里可以用向上调整算法进行建堆，时间复杂度为O（N*logN），也可以用向下调整算法进行建堆，时间复杂度为O（N）
- 注意这里的建堆和上文的建堆过程并不一样，上文的建堆过程是向内存申请空间，开辟了一个堆，然后往里填数据，这里的过程只是模拟其过程，并不用新开辟空间，而是在原本的空间上进行操作
向上调整建堆
- 我们从第一个结点开始，依次对每个结点进行向上调整
- i每加一次，就相当于与上文的数据的插入过程，然后对插入数据进行向上调整
- 这样等于每个结点都进行了一次向上调整，堆就建立好了
// 向上调整建堆
for (int i = 0; i <n; i++)
{
//AdjustUp里的大于号小于号决定了是大堆还是小堆
AdjustUp(hp,hp->a[i]);
}
向下调整建堆
- 因为向上/向下建堆的前提都是要在堆上进行，而数组一开始又不是一个堆，那怎么用向下建堆的方法将数组建成堆呢？
- 一个结点，即可以是大堆，也可以是小堆。
- 我们从最后一个非终端结点依次往左进行向下调整，这样我们遍历了除了最后一层的所有结点，也完成了堆的建立
// 向下调整建堆
for (int i = (n -1-1) / 2; i >= 0; i--)
{
adjustdown(a, n, i);
}
当堆建立好后，堆排序就很轻松了，相当于模拟堆的删除过程。这里以降序为例（建小堆）
原理
小堆的堆顶是最小值，将其与堆末尾的数据交换后，这样最小的元素就到了数组的末尾了。然后我们对这个处在数组最后一个位置的最小元素视而不见，将交换过去的堆顶元素执行向下调整算法，这时，第二小的元素就到了堆顶，然后此时的堆顶元素继续与最后一个元素进行交换 （注意第一个交换过去的最大的元素已经不在范围内了，也就是说每将一个当前最大的数交换过去后，可视作size减一一次） ，然后再将交换过去的堆顶元素执行向下调整算法…这样循环往复，最终该数组就变成了降序。
是不是非常amazing，这样就实现了一个N*logN的排序算法了
// 堆排序
void HeapSort(HPDataType* a, int n)
{
assert(a);
// 向下调整, 这里是建小堆
for (int i = (n - 2) / 2; i >= 0; i--) adjustdown(a, n, i);
//小堆即降序
int k = n - 1;
while (k > 0)
{
swap(&a[0], &a[k]);
adjustdown(a, k, 0);
k--;
}
}
动图演示：网上找了一个升序的，看看过程即可，小堆也是类似的。因为动图制作时间成本有点大，暂时就不自己弄了
Topk问题
- topk问题就是在成千上万的数据中找出排名靠前的前k个数据，什么热销榜好评榜都可以由堆来实现
- 因为只要求前k个，所以我们只要先将前k个数据建堆就好，不用将全部数据都建堆，不然会有很多的空间浪费
- 求前k个最小的建大堆，求前k个最大的建小堆
原理（以求前k个最小的为例）
先将前k个数据建堆，堆顶就是最大值，然后将其他数据与堆顶元素相比，如果比他小就将其与堆顶元素交换，然后就行向下调整。调整过后堆顶就是新的最大值了，然后再和下一个数据进行对比，如果比堆顶大，那就跳过该数据，让下一个数据进行与堆顶，如果小于堆顶，则将其与堆顶元素交换，然后就行向下调整.......r如此循环，就能求出前k个最小值了
总结：
- 求前k个最小值建大堆是为了依次把最大值都挑出去
- 求前k个最大值建小堆是为了依次把最小值挑出去
// topk问题
void PrintTopK(HPDataType* a, int n, int k)
{
assert(a);
// 开辟能够存放k个数据空间
HPDataType* topk = (HPDataType*)malloc(sizeof(HPDataType) * k);
if (topk == NULL)
{
perror("malloc fail");
exit(-1);
}
// 前k个数据进堆
memcpy(topk, a, sizeof(HPDataType) * k);
// 找前k个最小的——建大堆
for (int i = (k - 2) / 2; i >= 0; i--) adjustdown(topk, k, i);
// 对topk堆进行除大进小的操作
for (int i = k; i < n; i++)
{
if (a[i] < topk[0])
{
topk[0] = a[i];
adjustdown(topk, k, 0);
}
}
}
因为堆是很重要的数据结构，也很难，反复琢磨怎么讲的更细。所以本篇写了比较久，希望大家多多支持啦！！！
感谢阅读本小白的博客，如有错误请指出，一定虚心采纳~
完整代码
#include"Heap.h"
// 堆的构建
void HeapInit(Heap*hp)
{
assert(hp);
hp->capacity = hp->size = 0;
hp->a = NULL;
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
//满了先扩容
if (hp->capacity == hp->size)
{
int newcapacity = hp->capacity == 0 ? 4 : (hp->capacity * 2);
HPDataType *tmp=(HPDataType*)realloc(hp->a,sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail\n");
return;
}
hp->capacity = newcapacity;
hp->a = tmp;
}
hp->a[hp->size] = x;
hp->size++;
AdjustUp(hp,hp->size-1);
}
// 堆的删除
void HeapPop(Heap*hp)
{
assert(hp);
assert(!HeapEmpty(&hp));
Swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;
AdjustDown(hp, hp->size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(&hp));
return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->a[hp->size];
}
// 堆的判空
bool HeapEmpty(Heap* hp)
{
assert(hp);
return hp->size == 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
assert(hp);
hp->a = NULL;
hp->capacity = hp->size = 0;
}
//向上调整算法
void AdjustUp(Heap* hp, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (hp->a[child] < hp->a[parent])
{
Swap(&hp->a[child], &hp->a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整算法
void AdjustDown(Heap* hp, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
//从左右子树中找更小的一个孩子
if (child+1<n && hp->a[child] > hp->a[child+1])
{
child++;
}
if (hp->a[parent] > hp->a[child])
{
Swap(&hp->a[parent], &hp->a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}