文章目录
- 前言
- 一、什么是堆？
-
二、堆的实现
- 1.堆的结构
- 2.接口实现
- 总结
前言
堆(Heap)是计算机科学中一类特殊的数据结构，是最高效的优先级队列。堆通常是一个可以被看做一棵完全二叉树的数组对象。
一、什么是堆？
现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，
大根堆：根节点的数值总是大于等于（不小于）其左右节点的数值的二叉树
小根堆：根节点的数值总是小于等于（不大于）其左右节点的数值的二叉树
堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
二、堆的实现
1.堆的结构
//堆--数组实现--小根堆和大根堆
//小根堆--根节点的值小于其左右孩子节点的值
//大根堆--根节点的值大于其左右孩子节点的值
//以下实现以大根堆为例
typedef int HPDateType;
typedef struct Heap
{
HPDateType* a;
int size;//堆的元素个数
int capacity;//堆的容量
}Heap;
2.接口实现
1. 初始化
//初始化
void HPInit(Heap* php)
{
assert(php);
php->a = (HPDateType*)malloc(sizeof(HPDateType) * 4);
if (php->a == NULL)
{
perror("malloc fail");
return;
}
php->capacity = 4;
php->size = 0;
}2. 销毁
//销毁
void HPDestroy(Heap* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}3. 向上调整
//向上调整
void AdjustUp(HPDateType* a,int child)
{
//满足大根堆的性质--根节点数值大于其左右孩子中最大的那个
//前提：除了插入的元素其余的都保持着原有的性质
// 即只需要判断新插入节点数值是否大于其根节点
//已知孩子节点求其双亲计算公式：
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
//交换
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}向上调整：堆插入数据的调整方法，插入数据以后需要保持堆原有的性质，也是建堆的方式之一。其传递参数为孩子节点，利用孩子节点求取其双亲节点，同时因为其余的节点（除去插入数据以外的节点）都保持着其原有的性质，只需要依次比较插入的节点和双亲节点的数值，往复进行。
4. 插入
//插入
void HPPush(Heap* php, HPDateType x)
{
assert(php);
//判断是否需要扩容
if (php->size == php->capacity)
{
HPDateType* tmp = (HPDateType*)realloc(php->a, sizeof(HPDateType) * php->capacity * 2);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
//插入需要保证堆的性质不改变
//需要对插入元素进行向上调整，其左右子树性质才能不变
AdjustUp(php->a, php->size - 1);
}
插入数据：1.要进行判断是否需要扩容，
2.对新插入数据进行向上调整，以保证堆的性质不变
5. 向下调整
//向下调整
void AdjustDown(HPDateType* a, int size, int parent)
{
//大根堆性质：根节点的数值大于其左右孩子中较大的那个
//默认其左孩子较大
int child = parent * 2 + 1;
//当到达最后一个叶子节点时即可停止交换
while (child < size)
{
if (child + 1 < size && a[child] < a[child + 1])
{
//为什么要对chid+1进行判断？
//因为需要进行左右孩子的比较，防止越界
child++;
}
//定义在里面原因：需要每次都进行判断
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}参数讲解：1.size的作用：进行判断是否有数组越界访问
2.parent的作用：因为是需要对堆进行删除，要进行数据的交换，而仍旧需要保证堆本身的性质不变，传递parent数值，为确定其孩子节点的数值依旧小于其双亲节点
查漏补缺：1. 需要对于左右节点进行比较，因为大根堆，其根节点始终不小于其孩子节点，先比较出大的孩子节点，然后再进行孩子节点和双亲的比较
2. 需要利用size对child+1进行判断，保证不会越界访问
3. 循环终止条件：直至到最后一个叶子节点既可停止
6. 删除
//删除
void HPPop(Heap* php)
{
//删除的本意是对于堆进行修改，即删除堆顶元素
assert(php);
//交换堆顶元素和最后一个元素，然后进行删除
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
//保证堆的性质不发生改变--向下调整
AdjustDown(php->a, php->size, 0);
}删除需注意调用向下调整函数时，里面的size是减去交换堆顶元素，进行删除后的size
7. 其余接口
//返回堆顶元素
HPDateType HPTop(Heap* php)
{
assert(php);
return php->a[0];
}
//判空
bool HPEmpty(Heap* php)
{
assert(php);
return php->size == 0;
}
//返回元素个数
int HPSize(Heap* php)
{
assert(php);
return php->size;
}
void Swap(HPDateType* p1, HPDateType* p2)
{
HPDateType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
其余接口较为简单实现，只需要注意进行相关断言指针即可文章来源：https://www.toymoban.com/news/detail-431017.html
总结
堆，数据结构的一种很有用的结构，其不仅可以适用于存储数据，另外可以对数据进行排序，堆排序，一种非常高效的排序方式，在后续会进行介绍，身为学习者的我们需要对堆的实现做到胸有成竹，从而才能更好的使用。文章来源地址https://www.toymoban.com/news/detail-431017.html
到了这里，关于数据结构---堆的实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
