大小堆的实现（C语言）

目录

前言

一种完全二叉树：堆

堆的概念

堆的性质

建堆的时间复杂度

建堆的空间复杂度：

小堆的实现

必要补充

堆的初始化

堆的销毁

向上调整算法

堆的插入

向下调整算法

堆的删除

获取堆顶元素

获取堆中元素个数

堆的判空

最终代码

Heap.h文件

Heap.c文件

test.c文件

大堆的实现

思考：堆的意义是什么？

1、堆排序

2、top k问题

---

前言        

        在上一篇中，我们学习了二叉树的基本概念：C语言二叉树的基本概念（一）现在我们来学习一种完全二叉树堆，以及大小堆的实现......

一种完全二叉树：堆

堆的概念

概念：如果有一个关键码的集合K = { k0，k1，k2，…}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，若分别满足以下两种情况，则称该堆为小/大堆： 

根节点为最大值的堆叫做最大堆或大根堆，根节点为最小值的堆叫做最小堆或小根堆

堆的性质

1. 堆是一个完全二叉树；
2. 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值

建堆的时间复杂度

1、我们将一个高度为h的满二叉树转变成一个小堆，该小堆的结点总数为log(N+1)

一般来说对数的底我们将其忽略，所以这里原本是log(以2为底N+1的对数)

第一层的结点个数为2^0、第二层的结点个数为2^1......第h层的结点个数为2^(h-1)

结点总数为：2^0 + 2^1 +......+2^(h-1) = 2^h - 1 

（等比数列求和公式：Sn=a1 (1-q^n)/ (1-q)）
假设结点总数为N，则N与h的关系是N = 2^h - 1 == h = log(N+1)

即一个高h的满二叉树的结点个数为log(N+1)

2、进行堆的调整，得到最终的时间复杂度为O(N*logN)

第一层元素向上调整0次，第二层元素向上调整1次......第h层元素向上调整h-1次

同时每一层元素中的结点个数又分别为2^0、2^1......2^(h-1)

总调整次数T为：T = 2^0×0 + 2^1×1 +......2^(h-1)×(h-1)     ① 

利用错位相减法列出第二个式子：2*T = 2^1×0 + 2^2×1 +......2^h×(h-1)     ②

由① - ②得： T = 2 + 2^h * (h-2)     ③

将h = log（以2为底N+1的对数）代入③得④：

T = （N+1）log（以2为底N+1的对数）- 2 * N     ④

将④利用大O渐进表示法转换为 T(N) = O(N*log以2为底N的对数)

结论：建堆的时间复杂度为O(N*logN)

建堆的空间复杂度：

        小堆的空间复杂度为O(n)，其中n是小堆中元素的个数。在建堆的过程中，需要额外的空间来存储数组中的元素。

结论：建堆的空间复杂度为O(N)

小堆的实现

我们利用顺序表（顺序存储方式）实现堆

必要补充

堆的任何一个父结点的编号parent与其左孩子结点的编号leftchild满足如下关系式:

理解这里是我们后续在编写向上调整算法与向下调整算法时的基础 

堆的初始化

//初始化堆
void HeapInit(HP* php)
{//检查堆的有效性assetr(php);php->a = NULL;php->capacity = 0;php->size = 0;}

堆的销毁

free可以用来检查是否为空，若指针为空，则free不执行任何操作，指针不为空就释放内存空间

//堆的销毁
void HeapDestroy(HP* php)
{assert(php);//释放a指针的内存空间并将a指针置为空free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}

向上调整算法

//向上调整
void AdjustUP(HPDataType* a,int child)
{int parent = (child - 1) / 2;//当孩子等于0的时候它已经位于树顶了没有父亲了就应该结束循环while(child > 0){//if (a[child] > a[parent])，就是它if (a[child] < a[parent]){//如果儿子小于父亲就交换父子位置，同时将此时Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}//由于是写一个小堆，所以当孩子大于等于父亲时不需要交换，直接退出循环即可else{break;}}
}

堆的插入

//堆的插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容if (php->size == php->capacity){size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc error");return -1;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;//向上调整,从顺序表最后一个元素开始调整，该元素的下标为size-1AdjustUP(php->a, php->size - 1);}

每插入一个新的元素都需要进行一次向上调整的判断 

向下调整算法

//向下调整算法
void AdjustDown(HPDataType* a, int size, int parent)
{//根据之前的推论，左孩子的下标值为父亲下标值的两倍+1，左孩子的下标值为父亲下标值的两倍+2int child = parent * 2 + 1;//循环结束的条件是走到叶子结点while (child < size){//if (child + 1< size && a[child + 1] > a[child])，它也是//假设左孩子小，若假设失败则更新child，转换为右孩子小，同时保证child的下标不会越界if (child + 1< size && 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 HeapPop(HP* php)
{assert(php);assert(php->size > 0);//这里并不采用惯用的顺序表头删的办法（向前覆盖），因为那样会引起堆的顺序被完全打乱的问题，我们在这里选择交换堆顶元素与堆尾元素然后再进行一次顺序表的尾删（直接size--即可）Swap(&php->a[0], &php->a[php->size - 1]);php->size--;//在交换完并尾删完后，可能此时的堆并不能满足小堆的要求（堆顶元素比它的两个孩子都大），所以我们必须再次对堆进行调整，经过向下调整算法将堆恢复至小堆（由于是堆顶元素开始调整所以还需传入堆顶元素对应的下标0）AdjustDown(php->a, php->size, 0);
}

 每删除一个元素都需要进行一次向下调整的判断  

获取堆顶元素

//获取堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);//获取堆顶元素则堆里应该有元素，故首先要保证size不小于等于零assert(php->size > 0);//确定堆中有元素后返回a[0]即可return php->a[0];
}

获取堆中元素个数

//获取堆中元素个数
size_t HeapSize(HP* php)
{assert(php);//判断size大于零后返回size大小即可return php->size;
}

堆的判空

//堆的判空
bool HeapEmpty(HP* php)
{assert(php);//返回对php->size == 0的判断结果return php->size == 0;
}

最终代码

Heap.h文件

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>#pragma once
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;  //指向存储元素的指针int capacity;	//当前顺序表容量int size;		//当前顺序表的长度
}HP;//初始化堆
void HeapInit(HP* php);//销毁堆
void HeapDestroy(HP* php);//向上调整算法
void AdjustUP(HPDataType* a, int child);//堆的插入
void HeapPush(HP* php,HPDataType x);//向下调整算法
void AdjustDown(HPDataType* a, int child);//堆的删除（删除堆顶的数据）
void HeapPop(HP* php);//获取堆顶元素
HPDataType HeapTop(HP* php);//获取堆中元素个数
size_t HeapSize(HP* php);//堆的判空
bool HeapEmpty(HP* php);

Heap.c文件

#include "Heap.h"//初始化堆
void HeapInit(HP* php)
{//检查堆的有效性assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}//堆的销毁
void HeapDestroy(HP* php)
{assert(php);//释放a指针的内存空间并将a指针置为空free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}//交换父子位置
void Swap(HPDataType* p1,HPDataType* p2)
{HPDataType* tmp = *p1;*p1 = *p2;*p2 = tmp;
} //向上调整，此时传递过来的是最后一个孩子的元素下标我们用child表示
void AdjustUP(HPDataType* a,int child)
{//由于我们要调整父亲与孩子的位置所以此时也需要父亲元素的下标，而0父亲元素的下标值 = （任意一个孩子的下标值-1）/ 2 int parent = (child - 1) / 2;//当孩子等于0的时位于树顶（数组首元素的位置），树顶元素没有父亲，循环结束while(child > 0){//如果孩子还未到顶且它的下标对应的元素值小于它的父亲的下标对应的元素值，就将父子位置交换，交换玩后还要将下标对应的值“向上移动”//if (a[child] > a[parent])，就是它if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}//由于这是一个小堆，所以当孩子大于等于父亲时不需要交换，直接退出循环即可else{break;}}
}//堆的插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc error");return -1;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;//向上调整,从顺序表最后一个元素开始调整，该元素的下标为size-1AdjustUP(php->a, php->size-1);
}//向下调整算法
void AdjustDown(HPDataType* a, int size, int parent)
{//根据之前的推论，左孩子的下标值为父亲下标值的两倍+1，左孩子的下标值为父亲下标值的两倍+2int child = parent * 2 + 1;//循环结束的条件是走到叶子结点while (child < size){//假设左孩子小，若假设失败则更新child，转换为右孩子小，同时保证child的下标不会越界//if (child + 1 < size && a[child + 1] < a[child])，它也是if (child + 1 < size && 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 HeapPop(HP* php)
{assert(php);assert(php->size > 0);//这里并不采用惯用的顺序表头删的办法（向前覆盖），因为那样会引起堆的顺序被完全打乱的问题，我们在这里选择交换堆顶元素与堆尾元素然后再进行一次顺序表的尾删（直接size--即可）Swap(&php->a[0], &php->a[php->size - 1]);php->size--;//在交换完并尾删完后，可能此时的堆并不能满足小堆的要求（堆顶元素比它的两个孩子都大），所以我们必须再次对堆进行调整，经过向下调整算法将堆恢复至小堆（由于是堆顶元素开始调整所以还需传入堆顶元素对应的下标0）AdjustDown(php->a, php->size, 0);
}//获取堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);//获取堆顶元素则堆里应该有元素，故首先要保证size不小于等于零assert(php->size > 0);//确定堆中有元素后返回a[0]即可return php->a[0];
}//获取堆中元素个数
size_t HeapSize(HP* php)
{assert(php);//判断size大于零后返回size大小即可return php->size;
}//堆的判空
bool HeapEmpty(HP* php)
{assert(php);//返回对php->size == 0的判断结果return php->size == 0;
}

test.c文件

#include "Heap.h"int main()
{int arr[] = { 4,6,2,1,5,8,2,9 };int sz = sizeof(arr) / sizeof(arr[0]);HP hp;HeapInit(&hp);for (int i = 0;i < sz; ++i){HeapPush(&hp,arr[i]);}//堆不为空就获取堆顶元素并删除while (!HeapEmpty(&hp)){printf("%d ",HeapTop(&hp));HeapPop(&hp);}printf("\n");return 0;
}

大堆的实现

大堆的实现只需要将向上调整算法和向下调整算法中，只需要将注释掉的语句重新启用即可

思考：堆的意义是什么？

1、堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：建堆与利用堆删除思想进行排序

1. 建堆：升序：建大堆、降序：建小堆（很重要，下一篇我们会对升序建大堆的办法进行详细介绍）
2. 利用堆删除思想来进行排序：建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序（重要）

当一棵树为满二叉树时，高度h与结点总数N的关系是：h = log (N + 1)

当一棵树为完全二叉树时，高度h与结点总数N最坏的关系是：h = log N + 1

所以如果有一百万个数据组成一棵二叉树，那么这棵树的高度仅为20，十亿个数据，高度仅仅为30，即如果我们要用堆排序去查找100w个数据中的其中一个大概只需要查找二十次......

补充：在使用堆排序时，并不能说它能更高效地维护数据的有序性。相反，建立和调整一个完整的二叉树结构以及频繁进行元素交换和下沉操作可能会带来一些额外开销，并且在某些情况下可能比其他简单算法慢。但是，由于其稳定而可预测性能表现，在某些特殊情况下仍然被认为是有效和实用的算法之一。

2、top k问题

问题描述：获取N个数里找最大的前K个数（N远大于K）

解决思路一：

N个数插入进大堆中，Pop K次

时间复杂度：N*logN + K*logN == O(N*logN)

但如果N为100亿（100亿个整数需要40GB左右的内存空间），而只要查找前10个数（K为10）？ 

解决思路二：

1、取前K个值，建立K个数的小堆

2、再读取后面的值，跟堆顶元素比较，若大于堆顶元素，交换二者位置然后重新堆化成小堆

时间复杂度：O(N*logK)

注意事项：必须要建立小堆，不能建立大堆，如果建立大堆，一旦第一大的数字在建堆时位于堆顶，后续第n大的数字就无法进堆，同时第二大的数字可能还会被挤出去，如果不信可以用[4,6,1,2,8,9,5,3]这个我随机想出来数组用以上方法取前三个最大的数字试一试

        有时候你可能会很想刨根问底的知道这些办法都是怎么想出来的，其实我也不知道，这就跟你骑自行车的时候去思考这些链子为什么要这样组合在一起，为什么组合在一起就可以产生这样的效果，其实我们根本不需要思考那么多，我们只需要骑上自行车去干我们要干的事情即可，它只是一个用于解决我们问题的工具，我们说的解题思路也是一样的，这些东西都是哪些很nb的人发明出来的，如果你是一个很nb的人你也不会看到这里不是，前人栽树后人乘凉，作为一个还没有完全深入学习数据结构的菜鸟既然已经知道了有这种解决办法那么你就直接用，等你什么时候感觉自己已经很nb了再来思考为什么吧......（当然也不是说都不要思考一些必要的思考还是需要的）别钻牛角尖了🤡

模拟实现：

使用数组[7, 8, 15, 4, 20, 23, 2, 50]演示如何使用最小堆找出前3个最大的元素。

首先，我们创建一个最小堆，并将数组的前3个元素[7, 8, 15]插入堆中，初始堆的表示如下：

       7/   \8     15

接下来遍历数组，发现 4 < 7，因此我们不做任何操作

继续遍历数组，发现 20 > 7，因此将 7 替换为 20 并重新堆化成小堆

       8/   \20    15

继续遍历数组，发现 23 大于 8，因此我们将 8 替换为 23 并重新堆化成小堆

       15/    \20     23

继续遍历数组，发现 2 < 15，因此我们不做任何操作

继续遍历数组，发现 50 > 15，因此我们将 15 替换为 50 并重新堆化成小堆

       20/    \50     23

最后，数组遍历完成，得到了最终的最小堆

       20/    \50     23

此时，堆中的前3个最大元素为 `[20, 50, 23]`，它们就是原数组中的前3个最大元素

~over~