【数据结构篇C++实现】- 堆
文章目录
- 🚀一、堆的原理精讲
- ⛳（一）堆的概念
- ⛳（二）看图识最大堆
- ⛳（三）详解堆是用数组表示的树
- 🚀二、堆的向下调整算法
- 🚀三、堆的向上调整算法
- 🚀四、将任意一棵树建成堆
- 🚀五、堆的算法实现
- 1.堆的结构体定义
- 2.初始化堆
- 3.判断堆是否为空
- 4.插入新元素
- 5.堆顶元素出列（删除元素），同时获取堆顶数据
- 6.遍历打印堆
- 7.销毁堆
- 🚀六、拓展
- ⛳（一）用最大堆或最小堆来实现优先队列
- ⛳（二）堆排序算法
- ⛳（三）top - k问题
🚀一、堆的原理精讲
⛳（一）堆的概念
堆（Heap）：一种有特殊用途的数据结构——用来在一组变化频繁（发生增删查改的频率较高）的数据集中查找最值
- 堆中某个节点的值总是不大于或不小于其父节点的值;
- 堆总是一棵完全二叉树。
- 每个节点最多可以有两个节点
- 根结点的键值是所有堆结点键值中最大（小）者，且每个结点的值都比其孩子的值大（小），这样的堆叫最大（小）堆
- 除了根节点没有兄弟节点，最后一个左子节点可以没有兄弟节点，其他节点必须有兄弟节点
- 这里需要注意的是：在多个子树中，并不是说其中一个子树的父结点一定大于另一个子树的儿子结点。
实际上，先弄懂树这种数据结构再来看堆就会简单很多了，堆是你见过的最有个性的树！它是用数组表示的树。所以逻辑结构上其实是一棵树，物理结构上是一维数组，属于非线性结构
本篇博客默认你没有事先学过树，通俗易懂，讲解知识详细，即使不知道完全二叉树，也能辨认出堆，即使没学过树也能搞懂堆，本篇以最大堆进行讲解
⛳（二）看图识最大堆
图1：因为93 > 87，而且82无左子节点却有右子节点，不满足除了根节点和最后一个左子节点可以没有兄弟节点，其他节点必须要有兄弟节点的规定，所以图1不是堆
图2：82是最后一个左子节点，但92不是，而且没有兄弟节点，所以图2也不是堆
图3：满足条件，为最大堆
⛳（三）详解堆是用数组表示的树
i为下标，由上图我们能看出规律：
- i的左子节点：2i+1
- i的右子节点：2i+2
- i的父节点：(i-1)/2
这也就是我们在代码实现的时候需要注意的地方
🚀二、堆的向下调整算法
向下调整：是让调整的结点与其孩子节点进行比较，若想将其调整为小堆，那么根结点的左右子树必须都为小堆，
若想将其调整为大堆，那么根结点的左右子树必须都为大堆，有些文章说单纯满足为堆就行这种说法是不对的
向下调整算法的基本思想（大部分搜到的都是以最小堆为例，我就继续以最大堆为例了）：
- 从根结点处开始，选出左右孩子中值较大的孩子。
- 让大的孩子与其父亲进行比较。
- 若大的孩子比父亲还大，则该孩子与其父亲的位置进行交换。并将原来大的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
- 若大的孩子比父亲小，则不需处理了，调整完成，整个树已经是大堆了。
代码实现：
/*向下调整将当前的节点和子节点调整成最大堆*/
void adjustDown(Heap &heap, int index) {
int cur=heap.arr[index];//当前待调整的节点
int parent,child;
/*判断否存在大于当前节点子节点，如果不存在 ，则堆本身是平衡的，不需要调整；如果存在，则将最大的子节点与之交换，交换后，如果这个子节点还有子节点，则要继续按照同样的步骤对这个子节点进行调整*/
for(parent=index; (parent*2+1)<heap.size; parent=child) {
child=parent*2+1;
//取两个子节点中的最大的节点
if(((child+1)<heap.size)&&(heap.arr[child]<heap.arr[child+1])) {
child++;
}
//判断最大的节点是否大于当前的父节点
if(cur>=heap.arr[child]) {//不大于，则不需要调整，跳出循环
break;
}else {//大于当前的父节点，进行交换，然后从子节点位置继续向下调整
heap.arr[parent]=heap.arr[child];
heap.arr[child]=cur;
}
}
}
🚀三、堆的向上调整算法
向上调整：是让调整的结点与其父亲结点进行比较，当我们已经有一个堆，我们需要在堆的末尾插入数据，再对其进行调整，使其任然保持堆的结构，这里我们就需要用到堆的向上调整算法
向上调整算法的基本思想：
- 将目标结点与其父结点比较
- 若目标结点的值比其父结点的值大，则交换目标结点与其父结点的位置
- 将原目标结点的父结点当作新的目标结点继续进行向上调整。若目标结点的值比其父结点的值大，则停止向上调整，此时该树已经是大堆了。
代码实现：
/*将当前的节点和父节点调整成最大堆*/
void adjustUp(Heap &heap, int index) {
if(index<0 || index >= heap.size) {//大于堆的最大值直接 return
return;
}
while(index>0){
int temp = heap.arr[index];
int parent = (index - 1) / 2;
if(parent >= 0){//如果索引没有出界就执行想要的操作
if(temp > heap.arr[parent]){
heap.arr[index] = heap.arr[parent];
heap.arr[parent] = temp;
index = parent;
} else {//如果已经比父亲小 直接结束循环
break;
}
} else {//越界结束循环
break;
}
}
}
🚀四、将任意一棵树建成堆
前面我们已经知道，堆的向下调整算法是在基于根节点左右子树已经为最大堆或最小堆的前提下才能操作的；而堆的向上调整算法是在我们已经建好了一个最大堆或最小堆，用于插入元素后的调整
那么如何将任意一棵树建成最大（小）堆呢，这里我就改为：如何在数组中快速创建堆：
我们把向下调整算法倒着来，我们知道，满足堆，必须左右子树都是大堆或者小堆，我们可以利用这个思想，从下往上倒着走，从第一个非叶子节点开始，通过数组下标的控制，把它当做根去向下调整，依次往上，直到把当前路径调整成符合条件的大堆或者小堆即可
还是以最大堆为例讲解，可以看到，根节点右子树不是一个最大堆，所以不能直接用向下调整算法
- 首先我们需要找到最后一个结点的父结点如图（a），我们找到的结点是 87，然后找出该结点的最大子节点与自己比较，若该子节点比自身大，则将两个结点交换.。图(a)中，87 比左子节点 95 小,则交换之.如图（b）所示
- 我们移动到前一个父结点 93,如图©所示。同理做第一步的比较操作,结果不需要交换
- 继续移动结点到前一个父结点 82，82 小于右子节点 95，则 82 与 95 交换，如图(d)所示，82 交换后，其值小于左子节点，不符合最大堆的特点，故需要继续向下调整，如图(e)所示
- 所有节点交换完毕,最大堆构建完成
🚀五、堆的算法实现
1.堆的结构体定义
#define DEFAULT_CAPCITY 128
typedef struct _Heap{
int *arr; //存储堆元素的数组
int size; //当前已存储的元素个数
int capacity; //当前存储的容量
}Heap;
2.初始化堆
/*初始化堆*/
bool initHeap(Heap &heap, int *orginal, int size){
//orginal：原数据 size：数据个数 heap：堆
int capacity = DEFAULT_CAPCITY>size? DEFAULT_CAPCITY:size;
heap.arr = new int[capacity]; //分配堆中数组空间
if(!heap.arr) return false;
heap.capacity = capacity;
heap.size = 0;
//如果存在原始数据则构建堆
if(size>0){
memcpy(heap.arr, orginal, size*sizeof(int));
heap.size = size;
buildHeap(heap);
} else {
heap.size = 0;
}
return true;
}
/* 从最后一个父节点(size/2-1 的位置)逐个往前调整所有父节点（直到根节点）,确保每一个父节点都是一个最大堆，最后整体上形成一个最大堆 */
void buildHeap(Heap &heap){
int i;
for(i=heap.size/2-1; i>=0; i--){
adjustDown(heap, i);
}
}
解释：
- 初始化堆操作即为之前讲的将任意一棵树建成堆
- orginal为函数外传入的原数据，然后通过初始化将其建成堆
- buildHeap即为以最后一个非叶子节点开始的向下调整算法
3.判断堆是否为空
/*判断堆是否为空*/
bool isEmpty(Heap &heap){
if(heap.size<1) return true;
return false;
}
4.插入新元素
/*最大堆尾部插入节点，同时保证最大堆的特性*/
bool insert(Heap &heap, int value) {
if (heap.size == heap.capacity) {
fprintf(stderr, "栈空间耗尽！\n");
return false;
}
int index = heap.size;
heap.arr[heap.size++] = value;
adjustUp(heap, index);
return true;
}
5.堆顶元素出列（删除元素），同时获取堆顶数据
如果我们将堆顶的元素删除，那么顶部有一个空的节点，怎么处理？
我们先将堆顶的数据与最后一个数据交换位置，删除最后一个结点，然后再修复堆属性。
原因：我们若是直接删除堆顶的数据，那么原堆后面数据的父子关系就全部打乱了，需要全体重新建堆，时间复杂度为O（N）。若是用上述方法，那么只需要对堆进行一次向下调整即可，因为此时根结点的左右子树都是大堆，我们只需要在根结点处进行一次向下调整即可，时间复杂度为O ( log ( N ) ）
代码实现：
/* 删除堆顶元素，获取堆顶的数据*/
bool pop(PriorityQueue &pq, DataType &value) {
if (isEmpty(pq)) return false;
value = pq.arr[0];
pq.arr[0] = pq.arr[--pq.size];
//heap.arr[0] = heap.arr[heap.size-1];
//heap.size--;
adjustDown(pq, 0);// 向下执行堆调整
return true;
}
6.遍历打印堆
打印堆中的数据，这里用了两种打印格式。第一种打印格式是按照堆的物理结构进行打印，即打印为一排连续的数字。第二种打印格式是按照堆的逻辑结构进行打印，即打印成树形结构。
//求结点数为n的二叉树的深度
int depth(int n) {
assert(n >= 0);
if (n>0) {
int m = 2;
int hight = 1;
while (m < n + 1) {
m *= 2;
hight++;
}
return hight;
} else {
return 0;
}
}
//打印堆
void HeapPrint(Heap* php) {
assert(php);
//按照物理结构进行打印
int i = 0;
for (i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
//按照树形结构进行打印
int h = depth(php->size);
int N = (int)pow(2, h) - 1;//与该二叉树深度相同的满二叉树的结点总数
int space = N - 1;//记录每一行前面的空格数
int row = 1;//当前打印的行数
int pos = 0;//待打印数据的下标
while (1) {
//打印前面的空格
int i = 0;
for (i = 0; i < space; i++) {
printf(" ");
}
//打印数据和间距
int count = (int)pow(2, row - 1);//每一行的数字个数
while (count--)//打印一行
{
printf("%02d", php->a[pos++]);//打印数据
if (pos >= php->size)//数据打印完毕
{
printf("\n");
return;
}
int distance = (space + 1) * 2;//两个数之间的空格数
while (distance--)//打印两个数之间的空格
{
printf(" ");
}
}
printf("\n");
row++;
space = space / 2 - 1;
}
}
7.销毁堆
/*销毁堆*/
void destroy(Heap &heap){
if(heap.arr) delete[] heap.arr;
heap->arr = NULL;//及时置空
heap->size = 0;//元素个数置0
heap->capacity = 0;//容量置0
}
🚀六、拓展
⛳（一）用最大堆或最小堆来实现优先队列
操作系统内核作业调度是优先队列的一个应用实例，它根据优先级的高低而不是先到先服务的方式来进行调度；
如果最小键值元素拥有最高的优先级，那么这种优先队列叫作升序优先队列（即总是先删除最小的元素），类似的，如果最大键值元素拥有最高的优先级，那么这种优先队列叫作降序优先队列（即总是先删除最大的元素）；由于这两种类型是完全对称的，所以只需要关注其中一种，如升序优先队列
⛳（二）堆排序算法
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素.
(选择排序工作原理 - 第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零)
/* 实现堆排序 */
void heapSort(Heap &heap){
if (heap.size<1) return ;
while(heap.size>0){
int tmp = heap.arr[0];
heap.arr[0] = heap.arr[heap.size-1];
heap.arr[heap.size-1] = tmp;
heap.size--;
adjustDown(heap, 0);// 向下执行堆调整
}
}
⛳（三）top - k问题
若要从N个数字中取得最小的K个数字，则需要创建大小为K的大堆来获取。若要从N个数字中取得最大的K个数字，则需要创建大小为K的小堆来获取。
拜托，面试别再问我TopK了！！！_架构师之路-CSDN博客