堆 (带图详解)
开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第3天，点击查看活动详情 @TOC
1.堆的基本概念
1. 概念
如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
2.性质
1.必须为完全二叉树
在这里插入图片描述
2.满足大堆/小堆成立的条件
在这里插入图片描述
- 大堆：树中所有父亲节点都大于等于孩子节点
在这里插入图片描述
- 小堆：树中所有父亲节点都小于等于孩子节点
3.存储方式
1.逻辑结构
在这里插入图片描述
- 逻辑结构：我们想象出来的
2.物理结构
在这里插入图片描述
- 物理结构：实实在在在内存是如何存储的
4. 孩子与父亲之间下标的关系
在这里插入图片描述
- leftchild=parent*2+1
- rightchild=parent*2+2
- parent=(child-1)/2
这里child 可以是leftchild，也可以是rightchild，因为整数相除得到的结果也为整数
2.堆的基本实现
1.push——插入
1.代码
void adjustup(HPDatatype* a, int child)//向上调整算法
{
int parent = (child - 1) / 2;
while (child>0)
{
if (a[parent] >a[child])//以小堆为例
{
swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void heappush(HP* php, HPDatatype x)//插入
{
assert(php);
if (php->capacity == php->size)//扩容
{
HPDatatype* ptr = (HPDatatype*)realloc(php->a, sizeof(HPDatatype)*php->capacity * 2);
if (ptr != NULL)
{
php->a = ptr;
php->capacity *= 2;
}
}
php->a[php->size++] = x;//插入数据
adjustup(php->a,php->size-1); //向上调整
}2. 情况分析
在这里插入图片描述
由图可知目前是一个小堆
情况1
- 在数组后插入 >=56 的数 例如 100
在这里插入图片描述
此时依旧为一个小堆，不需要调整，直接插入在数组尾部就可以了
情况2
- 在数组后插入<56的数 例如 22
在这里插入图片描述
- 在圈中22比56小，所以不构成小堆，需要进行向上调整
3. 向上调整算法
1.过程分析
- 这里以小堆为例
在这里插入图片描述
- 我们要创建小堆，parent(56)>child(22)，所以要将两者值进行交换
在这里插入图片描述
- 假设我们并不知道上面的数 例如10 与 新交换后的parent 22 的关系 所以我们需要向上调整
在这里插入图片描述
- 即将 parent的下标赋给 child ，即22成为新的child下标对应位置，10成为parent下标对应位置 ，此时因为10<22，所以走break不需要调整
2. 临界条件的判断
在这里插入图片描述
- 当child下标处于0时，parent下标已经越界没有比较的必要了，所以child>0 就为临界条件
2. pop—— 删除
1.代码
void adjustdown(HPDatatype* a, int parent,int size)//向下调整算法
{
int child = parent * 2 + 1;//假设为左孩子
while (child<size)
{
if (child+1<size&&a[child] < a[child + 1])//如果假设不成立，就为右孩子
{
child++;
}
if (a[parent] < a[child])//孩子大于父亲
{
swap(&a[parent], &a[child]);
parent = child;
child=parent * 2 + 1;
}
else
{
break;
}
}
}
void heappop(HP* php)//删除
{
assert(php);
assert(php->size > 0);
swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
adjustdown(php->a,0,php->size);//向下调整算法
}2. 向下调整算法
1. 注意事项
在这里插入图片描述
在这里插入图片描述
若右孩子所对应没有结点，a[child+1]就会越界访问， 所以需要加上限制条件： child+1<size
2. 临界条件
在这里插入图片描述
- child作为下标存在，n为数据个数，child最多等于n-1
3.TOPK问题
- N个数，找最大/最小的前k个
这里我们以大堆来举例 寻找最大的前k个
在这里插入图片描述
1.过程分析
在这里插入图片描述
- 刚开始时，我们需要将首尾互换，并将此时的尾数据删除
在这里插入图片描述
- 交换parent下标与child下标所对应的值，如图1 2
- 并将child的下标赋给parent 如 图 2 3
3. create ——建堆
void heapcreate(HP* php, HPDatatype* a, int n)//建堆
{
assert(php);
php->a = (HPDatatype*)malloc(sizeof(HPDatatype) * n);
if (php->a == NULL)
{
perror("mealloc fail");
exit(-1);
}
memcpy(php->a, a, sizeof(HPDatatype) * n);
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
adjustdown(php->a, i, n);
}
}1.向下调整算法的应用
在这里插入图片描述
我们想创建一个大堆，就必须使左子树是一个大堆及右子树是一个大堆 所以要从倒数第二层开始调整
在这里插入图片描述
4. top—— 取堆顶元素
HPDatatype heaptop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}5. size—— 数据个数
int heapsize(HP* php)//数据个数
{
assert(php);
assert(php->size > 0);
return php->size;
}6. empty ——判空
bool heapempty(HP* php)//判断是否为空
{
assert(php);
assert(php->size > 0);
return php->size == 0;
}7. TOPK问题的具体实现
#include "heap.h"
int main()
{
HP php;
heapinit(&php);
int arr[] = {27,15,19,18,28,34,65,49,25,37};
int sz = sizeof(arr) / sizeof(arr[0]);
int i = 0;
for (i = 0; i < sz; i++)
{
heappush(&php, arr[i]);
}
print(&php);
int k = 5;//取前5个数
while (k--)
{
printf("%d ", heaptop(&php));
heappop(&php);
}
heapdestroy(&php);
return 0;
}
在这里插入图片描述
完整代码
1.heap.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDatatype;
typedef struct Heap
{
HPDatatype* a;
int size;
int capacity;
}HP;
void heapcreate(HP* php, HPDatatype *a, int size);
void heapinit(HP* php);//初始化
void heapdestroy(HP* php);//内存销毁
void heappush(HP* php,HPDatatype x);//插入
void heappop(HP* php);//删除
HPDatatype heaptop(HP* php);//堆顶数据
int heapsize(HP* php);//数据个数
bool heapempty(HP* php);//判断是否为空2.heap.c
#include"heap.h"
void heapcreate(HP* php, HPDatatype *a, int n)//建堆
{
assert(php);
php->a = (HPDatatype*)malloc(sizeof(HPDatatype) * n);
if (php->a == NULL)
{
perror("mealloc fail");
exit(-1);
}
memcpy(php->a, a, sizeof(HPDatatype) * n);
php->size = n;
php->capacity = n;
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
adjustdown(php->a, i, n);
}
}
void heapinit(HP* php)//初始化
{
assert(php);
php->a = (HP*)malloc(sizeof(php) *4);
php->size = 0;
php->capacity = 4;
}
void heapdestroy(HP* php)//内存销毁
{
assert(php);
free(php->a);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
void swap(HPDatatype* s1, HPDatatype* s2)
{
int tmp = 0;
tmp = *s1;
*s1 = *s2;
*s2 = tmp;
}
//void adjustup(HPDatatype* a, int child)//向上调整算法
//{
// int parent = (child - 1) / 2;
// while (child>0)
// {
// if (a[parent] >a[child])//以小堆为例
// {
// swap(&a[parent], &a[child]);
// child = parent;
// parent = (child - 1) / 2;
// }
// else
// {
// break;
// }
// }
//}
void adjustup(HPDatatype* a, int child)//向上调整算法
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[parent] < a[child])//以大堆为例
{
swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void heappush(HP* php, HPDatatype x)//插入
{
assert(php);
if (php->capacity == php->size)//扩容
{
HPDatatype* ptr = (HPDatatype*)realloc(php->a, sizeof(HPDatatype)*php->capacity * 2);
if (ptr != NULL)
{
php->a = ptr;
php->capacity *= 2;
}
}
php->a[php->size++] = x;//插入数据
adjustup(php->a,php->size-1); //向上调整
}
void adjustdown(HPDatatype* a, int parent,int size)//向下调整算法
{
int child = parent * 2 + 1;//假设为左孩子
while (child<size)
{
if (child+1<size&&a[child] < a[child + 1])//如果假设不成立，就为右孩子
{
child++;
}
if (a[parent] < a[child])//孩子大于父亲
{
swap(&a[parent], &a[child]);
parent = child;
child=parent * 2 + 1;
}
else
{
break;
}
}
}
void heappop(HP* php)//删除
{
assert(php);
assert(php->size > 0);
swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
adjustdown(php->a,0,php->size);//向下调整算法
}
HPDatatype heaptop(HP* php)//取堆顶元素
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
void print(HP* php)
{
int i = 0;
for (i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
bool heapempty(HP* php)//判断是否为空
{
assert(php);
assert(php->size > 0);
return php->size == 0;
}
int heapsize(HP* php)//数据个数
{
assert(php);
assert(php->size > 0);
return php->size;
}#include "heap.h"
int main()
{
HP php;
heapinit(&php);
int arr[] = {27,15,19,18,28,34,65,49,25,37};
int sz = sizeof(arr) / sizeof(arr[0]);
int i = 0;
for (i = 0; i < sz; i++)
{
heappush(&php, arr[i]);
}
print(&php);
int k = 5;
while (k--)
{
printf("%d ", heaptop(&php));
heappop(&php);
}
heapdestroy(&php);
return 0;
}3.test.c
#include "heap.h"
int main()
{
HP php;
int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
int sz = sizeof(arr) / sizeof(arr[0]);
int i = 0;
heapcreate(&php, arr, sz);
print(&php);
/*for (i = 0; i < sz; i++)
{
heappush(&php, arr[i]);
}
print(&php);*/
int k = 5;
while (k--)
{
printf("%d ", heaptop(&php));
heappop(&php);
}
heapdestroy(&php);
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-11-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
