【数据结构】堆（挑战从零基础到进阶）

 我们从概念开始一步步来学习堆，下面我们来从零基础来解剖该种数据结构。先提前透明：实现堆其实就是基于数组来实现一个完全二叉树而已 ！

---

目录

堆的概念

堆的性质

堆的物理逻辑&思维逻辑

堆的节点对应关系

堆的核心操作

（1）堆的数组结构

（2）堆的初始化操作

（3）堆的插入节点

  ●堆的插入：上浮调整

（4）堆的删除节点

  ●堆的删除：下沉调整

（5）堆的释放

堆的常见运用

堆的完整代码+思维逻辑

---

堆的概念

堆（Heap）是数据结构中一种特殊的计算机结构，是一种特殊的完全二叉树，为非线性的数据结构，一般用于优先队列、堆排序、Top-k的问题等等。下面是对完全二叉树的一个简单学习，有疑惑的朋友们可以看我的上一篇文章，里面详细的讲解了相关概念：【数据结构】二叉树

完全二叉树是二叉树中的一种，它的节点满足以下规律，有且只有以下三种情况：

1：有左右两个孩子     2：只有左孩子   3：没有孩子（叶子节点）

叶子节点只可能在最大的两层出现且在最左层的叶子节点都集中在左侧。如下图理解：

注意：除了最后一层，如果每个父节点的孩子节点都有两个，它属于满二叉树，注意区别！ 

堆的性质

结构特性：从上面我们可以观察到，除了一层外，其它层是满层的，最后一层居左对齐

堆序性质：可以看到，它的节点关键字是有序的，因此我们又可以将堆分为两类：

可以观察到大顶堆中，它的根节点关键字是整个树中是最大的，而每个父节点的孩子节点都要小于它的父节点。在小顶堆中，整个树的根节点关键字最小，且每个父节点关键字小于孩子节点的关键字。除此之外，有一个要补充的点：除了根节点的关键字处于两个极端之外，父节点的关键字是可以等于它的孩子节点的。下面我们进行精髓总结，方便记忆：

大顶堆：父节点的值>=子节点的值（根节点在整个树中最大）

小顶堆：父节点的值<=子节点的值（根节点在整个树中最小）

堆的物理逻辑&思维逻辑

咱们知道，堆是一种完全二叉树，但是我们选择的是数组方式的存储，没有用链表，可能有人想：如果我用数组实现堆，那么它的下标是不是就乱序了？并非如此，我们看下面这幅图：

我们的堆元素是依次存储到数组里面的，比如根节点对应数组下标1，根节点的左子节点对应数组的 2，根节点的右子节点对应数组的3，依次类推满足：从上到下，从左到右。思维逻辑方便我们在查找问题，以及写各种操作时借助二叉树来直观的体现，如果我们在数组上操作进行思维操作，那么会很乱，大家理解了吗！

堆的节点对应关系

因为我们是数组实现，节点下标之间的索引存在固定的数学关系：

如果堆在数组中的下标是从0开始，那么满足：

假如父节点在数组的下标为 i 它的左孩子节点在数组的下标为 2 * i+1，右节点数组下标为：2*i+2

如果堆在数组中的下标是从1开始，那么满足：

假如父节点在数组的下标为 i 它的左孩子节点在数组的下标为 2*i，右节点数组下标为：2*i+1

假如子节点在数组的下标为 k 它的父节点在数组中的下标为（k-1）/2

例如：

在左边的大顶堆中， 根节点在数组中的下标为1，那么它的左子节点在数组中的下标按照公式得出2*1=2，右孩子节点的数组下标为2*1+1=3，反过来，它的子节点的数组下标为3，它的根节点（父节点）数组下标为（3-1）/2=1。右边的小顶堆也是同理！

在右边的小顶堆中，根节点的数组下标从0开始 ，它的根节点（父节点）下标为0，那么它的左子节点下标按照公式为2*0+1=1，它的右子节点数组下标为2*0+2=2，反过来它的左子节点数组下标为1，那么它的父节点数组下标按照公式为（1-1）/2=0，同理，大顶堆也是如此！

堆的核心操作

首先我们需要用数组的形式来模拟完全二叉树，来依次完成下面的操作，时间复杂度都是logN：

初始化操作：初始化我们要开辟一定的空间，并返回这个指向这个空间的指针 

插入：向整个树中添加一个元素

           （1）上浮：进行调整新插入的元素路径

删除：不同的删除操作之后我们需要保证余下的元素满足堆的规则，因此需要下面两个操作：

           （1）下沉：调整删除后的堆顶元素路径

堆的销毁：我们会进行动态开辟，因此养成良好习惯，及时释放开辟的空间

上浮与下沉的作用说的通俗一些就是每次进行插入与删除操作后，通过它们来调节堆的节点，使它们满足堆的性质

（1）堆的数组结构

堆的数组结构，需要一个计算当前存储量的，还有一个指向动态数组空间指针，以及最大存储个数

下面我以根节点下标为0的大顶堆存储来进行举例！

#define MAX 10typedef struct Heap
{int size;//当前元素个数int MAX_size;//最大存储个数int* data;//动态存储空间
}Heap;

（2）堆的初始化操作

 初始化我们需要只需要让结构体里面的指针指向一片空间就可以，成员进行一些初始化设置，注意我们在这里实现的堆下标是从0开始，所以size初始化为-1。有的堆是从下标1开始，记得区分！

//初始化
void Preliminary(Heap*Newnode)
{Newnode->data = (Heap*)malloc(sizeof(Heap) * MAX);//空间有效性的判断if (Newnode->data == NULL){printf("空间开辟无效\n");return;}//初始化内容Newnode->size = -1;Newnode->MAX_size = MAX;
}

（3）堆的插入节点

在插入节点之前：我们应该判断空间是否支持插入，这里面涉及了判断NULL以及空间大小判断

在插入节点之后：因为我们写的是大顶堆，因此需要对刚插入的成员根据情况是否进行调整位置

按照大顶堆的规则，根节点的关键字应该是最大的，保证每个父节点都要比它的孩子节点大，同时为了以后方便维护我们需要另外写两个函数：上浮调整函数、交换函数 

//插入
void Inport(Heap* Newnode, int data)
{//判断空间是否存在if (Newnode == NULL){printf("空间无效\n");return;}//判断是否是满空间if (Newnode->size == Newnode->MAX_size){int * pc = (int *)realloc(Newnode->data, sizeof(Heap) * Newnode->size * 2);if (pc == NULL){printf("扩容失败\n");return;}//改变当前最大存储量Newnode->MAX_size += Newnode->MAX_size;//连接Newnode->data = pc;printf("扩容成功\n");}Newnode->size++;Newnode->data[Newnode->size] = data;//上浮调整Adjust(Newnode->data, Newnode->size);
}

  ●堆的插入：上浮调整

我们将这个新插入孩子节点下标传过去，注意是传址操作！然后算他的父节点下标位置，在用while循环来一直进行判断是否需要调整这个孩子节点和它的父子节点，这里需要理解循环的条件，已经调整完之后需要进行的两个操作，请看下面的代码：

//上浮调整
void Adjust(Heap* Newnode, int child)
{//计算父节点的关键字int parent = (child - 1) / 2;//判断是否需要交换while (child > 0){if (Newnode->data[child] > Newnode->data[parent]){//满足条件就交换Exchange(&Newnode->data[child], &Newnode->data[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}

//交换
void Exchange(Heap* p1, Heap* p2)
{Heap x = *p1;*p1 = *p2;*p2 = x;
}

（4）堆的删除节点

删除堆中的某个节点，咱们如果直接删除尾部的孩子节点，并没有什么意义，所以咱们来进行删头 ，也就是删除根节点，我们原先已经将堆按照大顶堆规则排列，那么我们如果删除头，取的是整个堆的最大元素，这非常适合排序！（时间复杂度是logN）

●堆的删除：下沉调整

那么重点来了：如果我们删除根节点，那么再去一个个摞另外的元素重新排列吗？不，这样效率很低。下面介绍一个方法：将根节点与最后一个孩子节点交换位置，然后元素个数size减一，接下来我们先说重新调整的一种方法：下沉 

上面是第一步：先交换两个元素，同时size减一

//删除
void Disposal(Heap* Newnode)
{//断言空指针assert(Newnode);//交换根节点与最后一个下标的孩子节点Exchange(&Newnode->data[0], &Newnode->data[Newnode->size]);Newnode->size--;//下沉调整Underneath(Newnode->data,Newnode->size);
}

下面进行最后一步：循环比较此时的根节点和它的孩子节点，哪个大交换哪个，如果小于孩子节点，就结束循环，下面是代码参照

//下沉调整
void Underneath(int *data,int size)
{int parent = 0;int child = 2 * parent + 1;//比较父节点（根节点）与它的最大的孩子节点while (child < size){//先避免越界，再比较两个孩子节点，找最大的if (child < size && data[child] < data[child+1]){++child;}if (data[child] > data[parent]){Exchange(&data[child], &data[parent]);//改变父节点下标parent = child;child = 2 * parent + 1;}else{break;}}
}

（5）堆的释放

咱们可以先释放元素，再释放开辟好的空间，这里注意释放的指针必须是指向空间的起始位置！

//堆的释放
void Free(Heap *Newnode)
{assert(Newnode);int num = 0;while (num <= Newnode->size){Newnode->data[num] = 0;num++;}//释放指针int* Node = Newnode->data;free(Node);Node = NULL;printf("释放成功");
}

堆的常见运用

1：优先队列

这是一种特殊的数据结构，它的排列是顺序是按照元素的优先级的，注意不是插入的顺序。它可以在O（1）的时间复杂度内获取当前优先级最高的元素，它的删除与插入与堆一样都是logN。堆结构可以快速实现插入和删除操作，采用的数组又降低了难度。

2：Top K问题

Top K问题就是从一堆数据中找到前K个最大、最突出的元素，这点是不是很适合堆！？比如在一堆杂乱的元素中找到前4个最大的元素，这里刚好可以借助调整的上浮、下沉操作来实现

3：堆排序

核心思想就是利用父节点优先级高于子节点的特性，将无序数据排序成有序数据，这点直接用堆的调整函数就可以实现！

堆的完整代码+思维逻辑

首先咱们定义了一个结构体，这个结构体里面肯定有一个指向动态空间的指针，接下来肯定要涉及动态开辟已经初始化操作。随之就是给这个空间存储数据，这个过程也很简单，因为咱们得底层逻辑还是数组，只需要按照下标一个个存进去就可以。之后考虑到存进去的元素不符合大顶堆的规定，我们需要写一个调整函数，每次放入一个值需要与它的父节点比较，看是否交换位置，来实现初步的堆。最后是删除操作，咱们删除堆的堆顶，删除之后考虑到如果移动整个堆，那样就会很麻烦，因此我们使用特殊的删除方法：堆尾与堆头互换，然后删除堆尾，也就是下标减一。其次就是重新排序，我们只需要取整个堆的最大值放在堆头即可。以上就是整个思维逻辑！

#define _CRT_SECURE_NO_WARNINGS 1
#include"text.h"int main()
{int data = 0;Heap Newnode;//初始化Preliminary(&Newnode);//插入for (int i = 10; i < 110; i += 10){data = i;Inport(&Newnode, data);}//删除Disposal(&Newnode);//打印Printf_t(Newnode);//堆的释放Free(&Newnode);return 0;
}

头文件：

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>#define MAX 10typedef struct Heap
{int size;//当前元素个数int MAX_size;//最大存储个数int* data;//动态存储空间
}Heap;//初始化
void Preliminary(Heap*Newnode);
//上浮调整
void Adjust(int* data, int child);
//插入
void Inport(Heap* Newnode, int data);
//下沉调整
void Underneath(int* data, int size);
//交换
void Exchange(int* p1, int* p2);
//删除
void Disposal(Heap* Newnode);
//打印
void Printf_t(Heap Newnode);
//堆的释放
void Free(Heap *Newnode);

函数实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include"text.h"//初始化
void Preliminary(Heap * Newnode)
{Newnode->data = (Heap*)malloc(sizeof(Heap) * MAX);//空间有效性的判断if (Newnode->data == NULL){printf("空间开辟无效\n");return;}//初始化内容Newnode->size = -1;Newnode->MAX_size = MAX;
}//交换
void Exchange(int* p1, int* p2)
{int x = *p1;*p1 = *p2;*p2 = x;
}//上浮调整
void Adjust(int* data, int child)
{//计算父节点的关键字int parent = (child - 1) / 2;//判断是否需要交换while (child > 0){if (data[child]>data[parent]){//满足条件就交换Exchange(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}//插入
void Inport(Heap* Newnode, int data)
{//判断空间是否存在if (Newnode == NULL){printf("空间无效\n");return;}//判断是否是满空间if (Newnode->size == Newnode->MAX_size){int * pc = (int *)realloc(Newnode->data, sizeof(Heap) * Newnode->size * 2);if (pc == NULL){printf("扩容失败\n");return;}//改变当前最大存储量Newnode->MAX_size += Newnode->MAX_size;//连接Newnode->data = pc;printf("扩容成功\n");}Newnode->size++;Newnode->data[Newnode->size] = data;//上浮调整Adjust(Newnode->data, Newnode->size);
}//下沉调整
void Underneath(int *data,int size)
{int parent = 0;int child = 2 * parent + 1;//比较父节点（根节点）与它的最大的孩子节点while (child < size){//先避免越界，再比较两个孩子节点，找最大的if (child < size && data[child] < data[child+1]){++child;}if (data[child] > data[parent]){Exchange(&data[child], &data[parent]);//改变父节点下标parent = child;child = 2 * parent + 1;}else{break;}}
}//删除
void Disposal(Heap* Newnode)
{//断言空指针assert(Newnode);//交换根节点与最后一个下标的孩子节点Exchange(&Newnode->data[0], &Newnode->data[Newnode->size]);Newnode->size--;//下沉调整Underneath(Newnode->data,Newnode->size);
}//打印
void Printf_t(Heap Newnode)
{if (Newnode.size == 0){printf("没有元素，无法打印\n");return;}int num = 0;printf("堆元素：");while (num <= Newnode.size){printf("%d ", Newnode.data[num]);num++;}printf("\n");
}
//堆的释放
void Free(Heap *Newnode)
{assert(Newnode);int num = 0;while (num <= Newnode->size){Newnode->data[num] = 0;num++;}//释放指针int* Node = Newnode->data;free(Node);Node = NULL;printf("释放成功");
}

                                                         拿走不谢！记得三连！