【数据结构 堆】超详细理解&&例题&&错题
创作时间:
作者:
@小白创作中心
【数据结构 堆】超详细理解&&例题&&错题
引用
CSDN
1.
https://blog.csdn.net/Sunfor_sun/article/details/145380561
数据结构 堆
前言
在计算机科学中，堆(Heap)是一种高效管理动态数据的树形结构，尤其擅长快速获取极值。无论是在操作系统的任务调度、游戏中的优先级处理，还是大数据场景下的TopK问题，堆都扮演着重要的角色。本文将从基本概念到应用场景，全面解析堆的设计思想与实现技巧，并通过对比其他数据结构揭示其独特优势。
一、堆的基本概念
1.1 堆的性质
堆是一种完全二叉树，满足以下性质：
- 堆序性：每个节点的值与其子节点满足特定关系
- 最大堆：父节点值 >= 子节点值（堆顶为最大值）
- 最小堆：父节点值 <= 子节点值（堆顶为最小值）
- 完全二叉树性质：除最后一层外，其他层节点全满，且最后一层节点从左到右填充
1.2 堆的表示
堆通常可以通过数组实现，利用完全二叉树的性质快速定位父子节点
优点：
- 节省存储空间（不需要存储指针）
- 直接计算父节点和字节点索引（避免递归或额外查找操作）
- 构建和操作更方便（可以高效地进行堆调整）
代码演示
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int size;
}Heap;
父子索引关系
父节点索引i--> 左子节点2i+1右子节点2i+2
子节点索引i--> 父节点(i-1)/2
二、堆的实现方式
2.1 自顶向下
void swap(int* a, int* b)
{
int* tmp = *a;
*a = *b;
*b = tmp;
}
//自底向上调整
void heapify_up(int heap[], int index)
{
int parent = (index - 1) / 2;
while (index > 0 && heap[index] > heap[parent])
{
swap(&heap[index], &heap[parent]);
index = parent;
parent = (index - 1) / 2;
}
}
//自顶向下建堆
void build_heap_top_down(int heap[], int n)
{
for (int i = 1; i < n; i++)
{
heapify_up(heap, i);
}
}
图像演示
2.2 自底向上
//自顶向下堆化
void heapify_down(int heap[], int i, int n)
{
int largest = i;
int right = 2 * i + 1;
int left = 2 * i + 2;
if (left < n && heap[left] > heap[largest])
{
largest = left;
}
if (right < n && heap[right] > heap[largest])
{
largest = right;
}
if (largest != i)
{
swap(&heap[i], &heap[largest]);
heapify_down(heap, largest, n);
}
}
//自底向上建堆
void build_heap_down_up(int heap[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
{
heapify_down(heap,i, n);
}
}
图像演示
三、堆的应用场景
3.1 优化队列
为什么用堆来优化队列？
普通队列只能按照入队顺序出队，无法做到优先级出队，而堆实现的队列可以做到一下优点
- 插入元素（使用向上调整）时间复杂度O(log N)
- 获取最大/小元素（直接返回堆顶）时间复杂度O(1)
- 删除最大/小元素(删除堆顶后向下调整) 时间复杂度O(log N)
代码演示
#include<stdio.h>
#define MAX_SIZE 100
typedef struct
{
int data[MAX_SIZE];
int size;
}PrioritQueue;
void swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void heapify_up(PrioritQueue* pq, int index)
{
while (index > 0)
{
int parent = (index - 1) / 2;
if (pq->data[parent] >= pq->data[index])
break;
swap(&pq->data[parent], &pq->data[index]);
index = parent;
}
}
void heapify_down(PrioritQueue *pq,int index)
{
int left, right,largest;
while (index * 2 + 1 < pq->size)
{
left = 2 * index + 1;
right = 2 * index + 2;
largest = index;
if (left < pq->size && pq->data[left] > pq->data[largest])
{
largest = left;
}
if (right < pq->size && pq->data[right] > pq->data[largest])
{
largest = right;
}
if (largest == index)
{
break;
}
swap(&pq->data[index], &pq->data[largest]);
index = largest;
}
}
//插入元素
void push(PrioritQueue* pq, int value)
{
if (pq->size >= MAX_SIZE)
{
printf("队列已满，无法插入！\n");
return;
}
pq->data[pq->size] = value;
heapify_up(pq, pq->size);
pq->size++;
}
//获取栈顶元素
int top(PrioritQueue* pq)
{
if (pq->size == 0)
{
printf("队列为空！\n");
return -1;
}
return pq->data[0];
}
//删除堆顶元素
void pop(PrioritQueue* pq)
{
if (pq->size == 0)
{
printf("队列为空！\n");
return;
}
pq->data[0] = pq->data[pq->size - 1];
pq->size--;
heapify_down(pq, 0);
}
void print_heap(PrioritQueue* pq) {
printf("当前优先队列: ");
for (int i = 0; i < pq->size; i++) {
printf("%d ", pq->data[i]);
}
printf("\n");
}
// 测试代码
int main() {
PrioritQueue pq = { .size = 0 };
push(&pq, 5);
push(&pq, 10);
push(&pq, 3);
push(&pq, 8);
push(&pq, 7);
print_heap(&pq);
printf("堆顶元素: %d\n", top(&pq));
pop(&pq);
print_heap(&pq);
return 0;
}
3.2 堆的排序
堆排序我们在之前的例子中就在不断运用，接下来我们一起通过一道题体现一下
void CreateNDate()
{
// 造数据
int n = 10000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (size_t i = 0; i < n; ++i)
{
int x = rand() % 1000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
//利用堆排序在文件中找TopK
void PrintTopK(int k);
思路：
读取前K个元素建堆：首先从文件中读取前K个元素，建立一个最小堆。堆顶是这K个元素中的最小值。
处理剩余元素：继续读取文件中的剩余元素，对于每个元素，如果它大于堆顶元素，则替换堆顶，并调整堆结构以维持最小堆的性质。
排序并输出结果：最后，将堆中的K个元素进行降序排序，输出结果
具体解决代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 调整最小堆
void adjustHeap(int* heap, int i, int size) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && heap[left] < heap[smallest]) {
smallest = left;
}
if (right < size && heap[right] < heap[smallest]) {
smallest = right;
}
if (smallest != i) {
swap(&heap[i], &heap[smallest]);
adjustHeap(heap, smallest, size);
}
}
// 用于qsort的比较函数，降序排列
int compare(const void* a, const void* b) {
return (*(int*)b - *(int*)a);
}
void PrintTopK(int k) {
FILE* fp = fopen("data.txt", "r");
if (fp == NULL) {
perror("fopen error");
return;
}
int* heap = (int*)malloc(k * sizeof(int));
if (heap == NULL) {
perror("malloc error");
fclose(fp);
return;
}
// 读取前k个数
int count = 0;
while (count < k && fscanf(fp, "%d", &heap[count]) == 1) {
count++;
}
// 如果文件中的数不足k个，调整k的值
if (count < k) {
k = count;
if (k == 0) {
free(heap);
fclose(fp);
return;
}
}
// 建立最小堆
for (int i = k / 2 - 1; i >= 0; --i) {
adjustHeap(heap, i, k);
}
// 处理剩余元素
int num;
while (fscanf(fp, "%d", &num) == 1) {
if (num > heap[0]) {
heap[0] = num;
adjustHeap(heap, 0, k);
}
}
// 对堆中的元素进行降序排序
qsort(heap, k, sizeof(int), compare);
// 输出结果
for (int i = 0; i < k; ++i) {
printf("%d ", heap[i]);
}
printf("\n");
free(heap);
fclose(fp);
}
// 测试代码
int main() {
// 生成数据
CreateNDate();
// 打印Top 10
PrintTopK(10);
return 0;
}
四、堆与其他数据结构的对比
4.1 堆vs数组
4.2 堆 vs 链表
4.3 堆 vs 二叉树
小结
堆凭借其极值访问O(1)和动态调整O(log n)的特性，在数据处理中占据独特地位。无论是排序、压缩，还是实时调度，堆都能以优雅的方式解决问题。理解堆的底层逻辑后，你甚至可以定制自己的堆结构（如支持动态权值的堆），以应对更复杂的场景。
热门推荐
古玉太阳神像的寓意、象征及其文化意义
蓝牙信标定位系统：原理、应用与常见问题解答
每日辟谣|鸡蛋到底煮几分钟才好吃？
运动后喝盐水好不好
为什么秋藕最补人？
泰晤士小镇一日游攻略，含游玩路线、景点介绍、美食攻略
无书记员模式庭审+AI法官助理，打造数字审判"金水模式"
从超女到影视剧宠儿：郁可唯的音乐逐梦之路
坐地铁逛西安！5号线沿途这么好玩儿
企业在线培训课程内容如何满足不同员工的需求？
有一天， 恐龙复活了……
视觉与味觉的完美融合：如何通过综合设计打造独特的餐饮体验
贵州断桥镇种植中药材头花蓼 带动群众增收致富
八字命理中如何识别和应对“情劫”
每天洗脸都要用洗面奶吗
走进中新广州知识城 | 广州开发区生物医药产业布局系列
走进中新广州知识城 | 广州开发区生物医药产业布局系列
广东建成全国规模最大职业教育体系之一，21地市高职院校全覆盖
如何选择合适的二手房房屋贷款方式？二手房房屋贷款有哪些政策和流程？
小红书国际版和国行版区别 小红书国际版和国行版有哪些区别
莫让“1元教学门诊”遇冷
战痘课堂！痘痘肌需要了解的小知识
小孩耵聍栓塞的四种处理方法
投资知识分享：如何通过市场分析提高投资决策的准确性
4个动作专攻内脏脂肪，每周只需锻炼3次，轻松告别腰腹赘肉
寅未暗合是什么意思，寅未暗合代表什么
宝可梦对战技巧：四种等比扣血招式的实战应用
脸上长黑点的预防方法
使用脱毛膏后留下黑点怎么办？专业医生给出7个处理建议
AI写作助力自媒体变现：探索多元盈利模式