【数据结构 堆】超详细理解&&例题&&错题
创作时间:
作者:
@小白创作中心
【数据结构 堆】超详细理解&&例题&&错题
引用
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)的特性，在数据处理中占据独特地位。无论是排序、压缩，还是实时调度，堆都能以优雅的方式解决问题。理解堆的底层逻辑后，你甚至可以定制自己的堆结构（如支持动态权值的堆），以应对更复杂的场景。
热门推荐
节能环保小窍门，日常生活中的绿色生活实践
秋冬养生：中医面部色诊帮你早发现健康隐患
补硒能消除甲状腺结节吗？
得了甲状腺疾病，补碘还是控碘？还能吃哪些海鲜？
景迈山打卡：普洱澜沧必游景点推荐
冬季自驾游普洱澜沧：从准备到返程全攻略
电动车夏季充电指南：避开五大误区，延长电池寿命
电动车突然断电怎么办？原因分析与解决方案
上海电力胡努特鲁电厂刷新发电纪录，展现“一带一路”建设新成果
德国歌德大学揭秘：高智商大脑的秘密
收回不义之财：正义之战
迎好运的30套红色穿搭，美到不行！
湖北春节十大特产推荐
普洱孟连：拍鸟爱好者的天堂
那柯里茶马古道古镇：一段活着的茶马古道历史
探秘太阳河：普洱的绿色宝藏
《奔跑吧》带火普洱雨林徒步！
国网上海电力：智能配用电大数据平台创新实践
上海电力土耳其胡努特鲁电厂刷新发电纪录
华晨宇新歌首发！2025湖南卫视春晚亮点抢先看
非遗文化遇上现代舞台：2025湖南卫视春晚的创新演绎
单依纯、刘宇宁将引爆2025湖南卫视春晚
上海电力加码西部新能源，长江电力成二股东
成都旅游全攻略：避坑大实话+超实用攻略
成都十大景点全攻略：从都江堰到大熊猫基地，领略天府之国的精华
创业期健康零食企业营销方案
赵本山《相亲》爆笑瞬间大集合！
《不差钱》：一个让小沈阳一夜成名的小品
柯洁与AlphaGo：从对决到共存
广东人最爱的猪肚鸡：秋冬滋补养生的美味传奇