详解堆
原创
1.什么是堆？？
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
堆就是一种完全二叉树
物理上是线性存储的 逻辑上是一个完全二叉树
其中数组下标计算父子关系公式显得尤为重要：
parent=(child-1)/2;
例如：15 25 30 这三组数据 parent是15 ，由于整形的（3-1）/2 =（4-1）/2 均为一，那么意味着利用孩子计算双亲数组下标位置的时候，利用以上公式即可求解。
堆的分类
2.向上/下调整算法
2.1算法意义
保证堆的结构
2.2初始化操作
#pragma once
#include <iostream>
#include <assert.h>
#include <stdlib.h>
using namespace std;
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;2.3向上调整（找祖先）（常用于堆的插入）
在堆的插入中：插入之前 先分清楚是什么堆 且插入的时候一定是往后插入 不可以改变堆的结构。
这个时候 数组下标公式的意义就体现出来了 这里建立一个小根堆
算法思路：（小堆）
1.先将元素插入到堆的末尾，即最后一个孩子之后
2.插入之后如果堆的性质遭到了破坏，将新插入节点顺着双亲往上调整到合适的位置即可
操作步骤：
a[10]->a[(10-1)/2]->比较->孩子小交换->a[4]->a[(4-1)/2]->比较->孩子小交换->a[1]->a[0]->孩子是小元素交换。
结束条件：
parent>0 继续 <0 终止 这样写对吗？？会发生死循环
所以利用孩子来进行循环的判断 只要孩子>0 那么就接着循环 孩子=0就终止了
void swap(HPDataType* p1, HPDataType* p2) { // 带上指针改变实参大小
HPDataType tmp=*p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(HPDataType* a,int child){
int parent = (child - 1) / 2;
while (child>0) //循环条件的判断是孩子>0
{
if (a[child] < a[parent])
{
//处理数字值
swap(&a[child], &a[parent]);
//将父亲的位置给了孩子 上面的函数只换了大小
child = parent;
//再令孩子的值-1/2给了父亲
parent = (child - 1) / 2;
}
else {
break;
}
}
}这是建立小堆的向上调整算法 若想建立大堆 那么循环中的小于改成大于即可
2.4向下调整（常用于能找到次大或者次小堆的删除算法）
条件：左子树右子树是大堆/小堆
在堆的删除中:父子关系和兄弟关系会混乱 那么向下调整就出现了（代价低 总不能一个一个遍历）
且只要交换堆顶和堆底的数据 --size 再令大的下来 写出循环即为堆的删除算法
算法思路：（小堆）
1.寻找小孩子（用来交换） 默认认为小孩子是左孩子
2.根节点左看看右看看找到小孩子并判断与之交换若小的孩子比父亲还小，则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
编辑
结束条件：
在循环中孩子的越界条件中已经恰好书写完毕 只要找不到小孩子 就算结束
void AdjustDown(HPDataType* a, int n,int parent) {
// 默认小孩子是左孩子
int minchild = parent * 2 + 1;
while (minchild < n) { // 担心越界
// 默认可能有误 && 担心小孩子+1越界
if (a[minchild + 1] < a[minchild] && minchild + 1 < n) {
minchild++;
}
if (a[minchild] < a[parent]) {
//更新数值
swap(&a[minchild], &a[parent]);
//更新下标
parent = minchild;
minchild = parent * 2 + 1;
}
else {
break;
}
}
}其中 若将if的< 改为大于 就是建立大堆的方法
3.堆排序（N*logN）--复杂度相当小的排序
首先将数组N个数建成一个堆 不利用数据结构堆的插入Push自行实现 巧了 向/上下调整建堆是可以成功建堆的（模拟插入过程）
3.1向上调整建堆
void Heapsort(int* a, int n) {
for (int i = 1; i < n; i++) {
AdjustUp(a, i);
}
}3.2向下调整建堆
条件：
这个相比于上一个调整是有前提的 必须左右都是小/大堆 不能凭空使用 若左右子树不是堆 最后一行是没必要调整的 一个叶子元素本身就是堆 那么从倒数第一个非叶子节点进行调整（最后一个节点的父亲 利用父子下标公式）当前位置调整好后 减减即可到前一个位置
编辑
//申明：改图来自博主2021dragon
图1~6的解释：
1->2: 89的小标是9 其父亲的下标为4 即10 那么先判断并调整10和89的位置关系
2->3: 找到之后减减操作就就可以找到左边的节点 并判断左节点以下的堆是否需要排序
3->4: 继续减减 找到76 同时找到小孩子12 且小孩子12比76要小 令76下来
4->5: 继续减减 54的小孩子是10 比较后发现也得下调
5->6: 继续减减 23的小孩子是10 继续令23下调
void Heapsort(int* a, int n) {
for (int i = ((n-1)-1)/2; i >=0; i--) { // 倒数第一个非子叶 最后一个下标为n-1节点的parent
AdjustDown(a,n,i);
}
}3.3向上/向下建堆复杂度的讲解：
T（n）就是运行时间：节点个数*最多的向下调整层数 每一层的相加就是答案
编辑
向下调整的时间复杂度：一个高度为h的树，总深度为
则需要调整的最坏情况也就这么多
向下建堆的复杂度：由错位相减可得，总复杂度为N
向上建堆的复杂度：也可以使用相同的错位相减，但由于最后一层节点及其多，故将最后一层需要调整的次数得出，大方向也就可以得知：第h层有2^h-1个节点需要调整h-1层 那么相乘 T（n）约等于 2^h*(h-1) 则向上调整建堆的复杂度为O（N*logN）
向下调整优势的地方在于：节点越多，需要调整的次数越少；越往上虽然调整的次数变多但是需要调整的节点变少 且最后一层的节点不需要调整 在一个完全二叉树中 最后一层的节点大概占有一半的节点个数
3.4为什么升序不用小堆？？
1.建立小堆2.成本较高的是无法依次找到较小的数 这是难点也是开辟空间成本较高的复杂点
3.5为什么升序使用大堆？？
1.建大堆
2.将第一个数字与最后位置（n-i）交换，并且将最后一个不看作堆
3.向下调整选出次大，后续调整的复杂度只有O（logN）的大小，相当的快
下面是第一次交换的代码：
int i = 0;
while (i < n) {
swap(&a[0], &a[n - 1]);
AdjustDown(a, n - 1, 0);
}代码解释：交换第一个数字和最后一个位置的数字，并且调整的时候不再是n 而是n-1 不将最后一个数字看作是堆中的元素了
完整代码：为保持一直循环往复的进行，将i的初始值给1，后续最后一个位置用n-i来提替代
void Heapsort(int* a, int n) {
for (int i = ((n-1)-1)/2; i >=0; i--) {
AdjustDown(a,n,i);
}
//选择数字
int i = 1;
while (i < n) {
swap(&a[0], &a[n - i]);
AdjustDown(a, n - i, 0);
++i;
}
}建立升序和降序的控制点在于 AdjustDown中的if大于小于的朝向
若是大于 则为大堆 就是升序
若是小于 则建立的为小堆 则为降序
4.Top-K问题 寻找N个数前k个最大的
算法思路：替换-->堆顶元素和后续遍历的N-K个数字替换；筛选-->向下调整
1.堆排序--O（N*logN）
2.堆选数
寻找前k个，虽然无序但本质上也可以理解为降序，那么就是建立小堆
3.用前K个数建立K个数的小堆
4.依次遍历后续N-K个数，比堆顶的数据大，就替换堆顶数据，向下调整进堆，这样就可以保证这K个数是前K个最大的（只要是最大的前K个来了，就会和堆顶替换，同时这个堆中也会向下调整把较大的扔下去，堆顶元素是混子本身，将其替换筛选）
void AdjustDown(HPDataType* a, int n, int parent) {
// 默认孩子
int minchild = parent * 2 + 1;
while (minchild < n) { // 担心越界
// 默认可能有误 && 担心小孩子+1越界
if (a[minchild + 1] < a[minchild] && minchild + 1 < n) {
minchild++;
}
if (a[minchild] < a[parent]) {
//更新数值
swap(&a[minchild], &a[parent]);
//更新下标
parent = minchild;
minchild = parent * 2 + 1;
}
else {
break;
}
}
} // 这里是小于 因为要建立小堆
void PrintTopK(HPDataType* a, int n, int k)
{
// 建k个数小堆
for (int parent = ((k - 1) - 1) / 2; parent >= 0; --parent) {
AdjustDown(a, k, parent);
}
// 继续读取后N-K
for (int i = k; i < n; i++) {
int val = a[i];
if (val > a[0])
{
a[0] = val;
AdjustDown(a, k, 0);//调整的是堆顶的元素
}
}
for (int i = 0; i < k; ++i)
{
printf("%d ", a[i]);
}
}
int main()
{
int a[] = { 1,5,6,7,8,10,421421414,5 };
int n = sizeof(a) / sizeof(int);
int k = 3;
PrintTopK(a, n, k);
return 0;
}5.堆的基本操作（插入删除是重点）
5.1初始化
堆的类型包括 存储数据的数组，堆中元素的个数，当前堆的最大容量
typedef int HPDataType;//堆中存储数据的类型
typedef struct Heap
{
HPDataType* a;//用于存储数据的数组
int size;//记录堆中已有元素个数
int capacity;//记录堆的容量
}HP;
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}5.2销毁堆
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}5.3打印堆
void HeapPrint(HP* php)
{
for (int i = 0; i < php->size; ++i)
{
printf("%d ", php->a[i]);
}
printf("\n");
}5.4堆的插入
数据插入时是插入到数组的末尾，即树形结构的最后一层的最后一个结点，所以插入数据后我们需要运用堆的向上调整算法对堆进行调整，使其在插入数据后仍然保持堆的结构
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 fail");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}5.5堆的删除
堆的删除，删除的是堆顶的元素，但是这个删除过程可并不是直接删除堆顶的数据，而是先将堆顶的数据与最后一个结点的位置交换，然后再删除最后一个结点，再对堆进行一次向下调整。
原因：若是直接删除堆顶的数据，那么父子关系就全部打乱了，需要全体重新建堆。若是用上述方法，那么只需要对堆进行一次向下调整即可，因为此时根结点的左右子树都是小堆，我们只需要在根结点处进行一次向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
int minChild = parent * 2 + 1;
while (minChild < n)
{
// 找出小的那个孩子
if (minChild+1 < n && a[minChild + 1] < a[minChild])
{
minChild++;
}
if (a[minChild] < a[parent])
{
Swap(&a[minChild], &a[parent]);
parent = minChild;
minChild = parent * 2 + 1;
}
else
{
break;
}
}
}5.6获取堆顶元素
HPDataType HeapTop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
return php->a[0];
}5.7堆的判空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}5.8获取堆顶元素
int HeapSize(HP* php)
{
assert(php);
return php->size;//返回堆中数据个数我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖!
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
