【数据结构 堆】超详细理解&&例题&&错题
创作时间:
作者:
@小白创作中心
【数据结构 堆】超详细理解&&例题&&错题
引用
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)的特性，在数据处理中占据独特地位。无论是排序、压缩，还是实时调度，堆都能以优雅的方式解决问题。理解堆的底层逻辑后，你甚至可以定制自己的堆结构（如支持动态权值的堆），以应对更复杂的场景。
热门推荐
揭秘“婴幼儿成长陪伴师”：从技能培训到职业认同
修建泰缅“死亡铁路”：日军刺刀下，战俘和劳工死亡率近40%
餐桌椅什么颜色好看，提升居家格调的色彩搭配技巧
改善家庭关系的四大沟通策略
维权途径怎么选
眼底出血的12种原因
110kv电缆：电力传输的坚实脊梁
锂电池和铅酸电池：24V储能系统哪个更好？
跟不合理限速说再见，高速实行统一限速标准，车主：早这样多好
如何让鞋子的寿命更长久
小狗眼屎多是怎么回事？揭秘背后原因
2025年：勇于把握趋势性的投资机会
中国足球史上最具创造力的10位球星，武磊和范志毅也无缘榜首
血清免疫球蛋白G的作用
北京冰雪旅游季：三大区域特色景点全攻略
梦幻西游手游宠物玩法全攻略：从入门到精通
欧科云链研究院资深研究员蒋照生：计息稳定币带来监管新挑战
甲流高发季来临，这些防护要点请收好
YOLOv8目标检测优化：添加GAM注意力机制与Wise-IoU提升检测效果
潘姓起源与迁徙历史：古代名人、家规家训及现代分布
沙特：“石油王国”经济多元化势成
手机充电慢了怎么办
粤宏远A拟20亿跨界收购博创智能，转型高端装备制造能否成功？
未来车载HMI设计：VR与AR技术融合应用前景展望
写字楼配套业态有哪些？
模糊匹配在 Power Query 中的工作原理
福建安溪湖头镇：全域生态旅游焕新彩，古韵新风醉游人
春日限定丨这份武隆旅游攻略，速速码住！
如何切橙子（4种方法）
禄存星在命宫的含义与影响