数据结构之堆详解
创作时间:
作者:
@小白创作中心
数据结构之堆详解
引用
CSDN
1.
https://m.blog.csdn.net/sakura_ding/article/details/142313569
堆（Heap）是数据结构中一种重要的树形结构，常用于实现优先队列等数据结构。本文将详细介绍堆的基本概念、性质以及其实现方法，包括向上调整和向下调整算法，以及堆的创建、插入和删除操作。
二叉树的顺序结构
普通的二叉树不适合用数组来存储，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。
现实中我们通常把堆（一种二叉树）使用顺序结构的数组来存储，
需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
堆的概念及结构
如果有一个关键码的集合K = { k0，k1，k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：ki<=k2i+1且 ki<=k2*i+2( ki>=k2i+1且 ki>=k2*i+2) i = 0，1，2…，则称为小堆(或大堆)。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
堆的实现
堆向下调整算法
现在我们给出一个数组，逻辑上看做一颗完全二叉树。
我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
int array[] = {27,15,19,18,28,34,65,49,25,37};
//堆向上调整算法
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0)
while(child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
//堆向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
// 假设法，选出左右孩子中小的那个孩子
if (child+1 < n && a[child + 1] < a[child])
{
++child;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
请注意：
父子存储位置的下标规律：
leftchild=parent*2+1;
rightchild=parent*2+2;
parent=(parent-1)/2;
堆的创建
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。
根节点左右子树不是堆，我们怎么调整呢？
这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
int a[] = {1,5,3,8,7,6};
void HPInitArray(HP* php, HPDataType* a, int n)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
perror("malloc fail");
return;
}
memcpy(php->a, a, sizeof(HPDataType) * n);
php->capacity = php->size = n;
// 向上调整，建堆 O(N*logN)
//for (int i = 1; i < php->size; i++)
//{
// AdjustUp(php->a, i);
//}
// 向下调整，建堆 O(N)
for (int i = (php->size-1 - 1)/2; i >= 0; i--)
{
AdjustDown(php->a, php->size, i);
}
}
建堆时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
堆的插入
先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。
void HPPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size-1);
}
堆的删除
删除堆是删除堆顶的数据，将堆顶的数据跟最后一个数据交换，然后删除数组最后一个数据，再进行向下调整算法。
void HPPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
堆的代码实现
Heap.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
#include<time.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void HPInit(HP* php);
void HPInitArray(HP* php, HPDataType* a, int n);
void HPDestroy(HP* php);
// 插入后保持数据是堆
void HPPush(HP* php, HPDataType x);
HPDataType HPTop(HP* php);
// 删除堆顶的数据
void HPPop(HP* php);
bool HPEmpty(HP* php);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
void Swap(HPDataType* px, HPDataType* py);
Heap.c
#include"Heap.h"
void HPInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
void HPInitArray(HP* php, HPDataType* a, int n)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
perror("malloc fail");
return;
}
memcpy(php->a, a, sizeof(HPDataType) * n);
php->capacity = php->size = n;
// 向上调整，建堆 O(N*logN)
//for (int i = 1; i < php->size; i++)
//{
// AdjustUp(php->a, i);
//}
// 向下调整，建堆 O(N)
for (int i = (php->size-1 - 1)/2; i >= 0; i--)
{
AdjustDown(php->a, php->size, i);
}
}
void HPDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0)
while(child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
// 时间复杂度：
void HPPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size-1);
}
HPDataType HPTop(HP* php)
{
assert(php);
return php->a[0];
}
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
// 假设法，选出左右孩子中小的那个孩子
if (child+1 < n && a[child + 1] < a[child])
{
++child;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 时间复杂度：logN
void HPPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
热门推荐
漫威终极逆转：银河护卫队反派卡牌攻略
Excel打印签到表的完整指南：从基础设置到高级技巧
小说《西游记》中的唐僧，经历了哪些转变，成为一代“圣愚”的？
“货”力全开，从南宁“飞”向东盟！
谢安：东晋的杰出政治家与淝水之战的英雄
谢安：东晋的"稳健大师"，一位"政治界的佛系大师"
海贼王：恶魔果实的深度解析
常吃枸杞，能给身体带来哪些好处？有何“禁忌”？吃之前要清楚
空气能热水器制热揭秘：节能高效源于热泵技术
整形项目效果评估：科学、安全与美观的全面考量
破解“内卷式竞争”，建立“有为政府”的合理边界是关键
财富预测与八字命理分析，探索财富增长的奥秘
多重利好加持！“牛市旗手”迎投资机会？
夏日限定，漫画里的仲夏夜不过如此
一寸等于多少厘米？这个换算知识超实用！
业主签约闭口合同：法律风险与注意事项
我国自动驾驶行业分析：投融资集中产业链中下游 2025年或是L3“爆发年”
藕粉 PK 葛根粉：功效、口感大揭秘，谁才是你的养生首选？
药刺激胃吃什么缓解
二甲基硅油不同浓度都有哪些应用呢？
风湿病饮食禁忌知多少
类风湿性关节炎：运动和饮食管理全攻略
焊接方法的优缺点比较
新手爸妈指南：宝宝安稳睡眠的实用建议与技巧
房屋朝向怎么认定
深圳湾口岸地铁开通：港人过关后步行百米即可搭乘
追尾事故处理全攻略：证据保留、交强险赔付与法律判罚
掌握交通事故停车方法，确保行车安全
2024-2025年英语分层教学计划
冥想音乐如何促进深度睡眠？