【数据布局】堆（寻衅从零根本到进阶）

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

---

目次
堆的概念
堆的性子
堆的物理逻辑&头脑逻辑
堆的节点对应关系
堆的核心利用
（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的大顶堆存储来举行举例！

1. #define MAX 10
3. typedef struct Heap
4. {
5.         int size;//当前元素个数
6.         int MAX_size;//最大存储个数
7.         int* data;//动态存储空间
8. }Heap;

复制代码

（2）堆的初始化利用

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

1. //初始化
2. void Preliminary(Heap*Newnode)
3. {
4.         Newnode->data = (Heap*)malloc(sizeof(Heap) * MAX);
5.         //空间有效性的判断
6.         if (Newnode->data == NULL)
7.         {
8.                 printf("空间开辟无效\n");
9.                 return;
10.         }
12.         //初始化内容
13.         Newnode->size = -1;
14.         Newnode->MAX_size = MAX;
15. }

复制代码

（3）堆的插入节点

在插入节点之前：我们应该判断空间是否支持插入，这内里涉及了判断NULL以及空间巨细判断
在插入节点之后：由于我们写的是大顶堆，因此必要对刚插入的成员根据情况是否举行调解位置
按照大顶堆的规则，根节点的关键字应该是最大的，包管每个父节点都要比它的孩子节点大，同时为了以后方便维护我们必要别的写两个函数：上浮调解函数、交换函数 

1. //插入
2. void Inport(Heap* Newnode, int data)
3. {
4.         //判断空间是否存在
5.         if (Newnode == NULL)
6.         {
7.                 printf("空间无效\n");
8.                 return;
9.         }
10.         //判断是否是满空间
11.         if (Newnode->size == Newnode->MAX_size)
12.         {
13.                 int * pc = (int *)realloc(Newnode->data, sizeof(Heap) * Newnode->size * 2);
14.                 if (pc == NULL)
15.                 {
16.                         printf("扩容失败\n");
17.                         return;
18.                 }
19.                 //改变当前最大存储量
20.                 Newnode->MAX_size += Newnode->MAX_size;
21.                 //连接
22.                 Newnode->data = pc;
23.                 printf("扩容成功\n");
24.         }
25.         Newnode->size++;
26.         Newnode->data[Newnode->size] = data;
27.         //上浮调整
28.         Adjust(Newnode->data, Newnode->size);
29. }

复制代码

  ●堆的插入：上浮调解

我们将这个新插入孩子节点下标传已往，注意是传址利用！然后算他的父节点下标位置，在用while循环来不绝举行判断是否必要调解这个孩子节点和它的父子节点，这里必要明白循环的条件，已经调解完之后必要举行的两个利用，请看下面的代码：

1. //上浮调整
2. void Adjust(Heap* Newnode, int child)
3. {
4.         //计算父节点的关键字
5.         int parent = (child - 1) / 2;
7.         //判断是否需要交换
8.         while (child > 0)
9.         {
10.                 if (Newnode->data[child] > Newnode->data[parent])
11.                 {
12.             //满足条件就交换
13.                         Exchange(&Newnode->data[child], &Newnode->data[parent]);
14.                         child = parent;
15.                         parent = (child - 1) / 2;
16.                 }
17.                 else
18.                         break;
19.         }
20. }

复制代码

1. //交换
2. void Exchange(Heap* p1, Heap* p2)
3. {
4.         Heap x = *p1;
5.         *p1 = *p2;
6.         *p2 = x;
7. }

复制代码

（4）堆的删除节点

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

那么重点来了：如果我们删除根节点，那么再去一个个摞别的的元素重新分列吗？不，如许服从很低。下面先容一个方法：将根节点与末了一个孩子节点交换位置，然后元素个数size减一，接下来我们先说重新调解的一种方法：下沉 

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

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

复制代码

下面举行末了一步：循环比力此时的根节点和它的孩子节点，哪个大交换哪个，如果小于孩子节点，就竣事循环，下面是代码参照

1. //下沉调整
2. void Underneath(int *data,int size)
3. {
4.         int parent = 0;
5.         int child = 2 * parent + 1;
6.         //比较父节点（根节点）与它的最大的孩子节点
7.         while (child < size)
8.         {
9.                 //先避免越界，再比较两个孩子节点，找最大的
10.                 if (child < size && data[child] < data[child+1])
11.                 {
12.                         ++child;
13.                 }
14.                 if (data[child] > data[parent])
15.                 {
16.                         Exchange(&data[child], &data[parent]);
17.                         //改变父节点下标
18.                         parent = child;
19.                         child = 2 * parent + 1;
20.                 }
21.                 else
22.                 {
23.                         break;
24.                 }
25.         }
26. }

复制代码

（5）堆的开释

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

1. //堆的释放
2. void Free(Heap *Newnode)
3. {
4.         assert(Newnode);
6.         int num = 0;
7.         while (num <= Newnode->size)
8.         {
9.                 Newnode->data[num] = 0;
10.                 num++;
11.         }
12.         //释放指针
13.         int* Node = Newnode->data;
14.         free(Node);
15.         Node = NULL;
16.         printf("释放成功");
17. }

复制代码

堆的常见运用

1：优先队列
这是一种特别的数据布局，它的分列是次序是按照元素的优先级的，注意不是插入的次序。它可以在O（1）的时间复杂度内获取当前优先级最高的元素，它的删除与插入与堆一样都是logN。堆布局可以快速实现插入和删除利用，接纳的数组又低沉了难度。

2：Top K题目
Top K题目就是从一堆数据中找到前K个最大、最突出的元素，这点是不是很得当堆！？好比在一堆紊乱的元素中找到前4个最大的元素，这里刚好可以借助调解的上浮、下沉利用来实现
3：堆排序
核心头脑就是使用父节点优先级高于子节点的特性，将无序数据排序成有序数据，这点直接用堆的调解函数就可以实现！
堆的完备代码+头脑逻辑

起首咱们界说了一个布局体，这个布局体内里肯定有一个指向动态空间的指针，接下来肯定要涉及动态开辟已经初始化利用。随之就是给这个空间存储数据，这个过程也很简单，由于咱们得底层逻辑还是数组，只必要按照下标一个个存进去就可以。之后思量到存进去的元素不符合大顶堆的规定，我们必要写一个调解函数，每次放入一个值必要与它的父节点比力，看是否交换位置，来实现开端的堆。末了是删除利用，咱们删除堆的堆顶，删除之后思量到如果移动整个堆，那样就会很贫苦，因此我们使用特别的删除方法：堆尾与堆头交换，然后删除堆尾，也就是下标减一。其次就是重新排序，我们只必要取整个堆的最大值放在堆头即可。以上就是整个头脑逻辑！

1. #define _CRT_SECURE_NO_WARNINGS 1
2. #include"text.h"
4. int main()
5. {
6.         int data = 0;
7.         Heap Newnode;
8.         //初始化
9.         Preliminary(&Newnode);
10.         //插入
11.         for (int i = 10; i < 110; i += 10)
12.         {
13.                 data = i;
14.                 Inport(&Newnode, data);
15.         }
16.         //删除
17.         Disposal(&Newnode);
18.         //打印
19.         Printf_t(Newnode);
20.         //堆的释放
21.         Free(&Newnode);
22.         return 0;
23. }

复制代码

头文件：

1. #pragma once#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>#include<stdlib.h>#include<assert.h>#define MAX 10
3. typedef struct Heap
4. {
5.         int size;//当前元素个数
6.         int MAX_size;//最大存储个数
7.         int* data;//动态存储空间
8. }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);

复制代码

函数实现：

1. #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;                }                else                        break;        }}//插入
2. void Inport(Heap* Newnode, int data)
3. {
4.         //判断空间是否存在
5.         if (Newnode == NULL)
6.         {
7.                 printf("空间无效\n");
8.                 return;
9.         }
10.         //判断是否是满空间
11.         if (Newnode->size == Newnode->MAX_size)
12.         {
13.                 int * pc = (int *)realloc(Newnode->data, sizeof(Heap) * Newnode->size * 2);
14.                 if (pc == NULL)
15.                 {
16.                         printf("扩容失败\n");
17.                         return;
18.                 }
19.                 //改变当前最大存储量
20.                 Newnode->MAX_size += Newnode->MAX_size;
21.                 //连接
22.                 Newnode->data = pc;
23.                 printf("扩容成功\n");
24.         }
25.         Newnode->size++;
26.         Newnode->data[Newnode->size] = data;
27.         //上浮调整
28.         Adjust(Newnode->data, Newnode->size);
29. }
30. //下沉调整
31. void Underneath(int *data,int size)
32. {
33.         int parent = 0;
34.         int child = 2 * parent + 1;
35.         //比较父节点（根节点）与它的最大的孩子节点
36.         while (child < size)
37.         {
38.                 //先避免越界，再比较两个孩子节点，找最大的
39.                 if (child < size && data[child] < data[child+1])
40.                 {
41.                         ++child;
42.                 }
43.                 if (data[child] > data[parent])
44.                 {
45.                         Exchange(&data[child], &data[parent]);
46.                         //改变父节点下标
47.                         parent = child;
48.                         child = 2 * parent + 1;
49.                 }
50.                 else
51.                 {
52.                         break;
53.                 }
54.         }
55. }
56. //删除
57. void Disposal(Heap* Newnode)
58. {
59.         //断言空指针
60.         assert(Newnode);
62.         //交换根节点与最后一个下标的孩子节点
63.         Exchange(&Newnode->data[0], &Newnode->data[Newnode->size]);
64.         Newnode->size--;
66.         //下沉调整
67.         Underneath(Newnode->data,Newnode->size);
68. }
69. //打印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");}//堆的释放
70. void Free(Heap *Newnode)
71. {
72.         assert(Newnode);
74.         int num = 0;
75.         while (num <= Newnode->size)
76.         {
77.                 Newnode->data[num] = 0;
78.                 num++;
79.         }
80.         //释放指针
81.         int* Node = Newnode->data;
82.         free(Node);
83.         Node = NULL;
84.         printf("释放成功");
85. }

复制代码

                                                         拿走不谢！记得三连！