信息学竞赛数据结构——堆和堆排序及优先队列

堆和堆排序及优先队列

教学目录

1. 完全二叉树
2. 堆
3. 小根堆
4. 大根堆
5. 堆排序
6. 合并果子
7. 优先队列
8. 课程小结

一、完全二叉树

知识点

•完全二叉树的定义
除最后一层外，每一层都被完全填满，最后一层节点从左到右连续排列。
•数组存储优势
可用数组紧凑存储，无需指针，父子节点通过下标计算关系。
•下标映射规则
• 若根节点下标为 1，父节点下标为i。
• 左子节点下标为2*i，右子节点下标为2*i+1。

结构示意

完全二叉树的形态，数字为数组下标：

1 ← 第1层（根节点） / \ 2 3 ← 第2层 / \ / \ 4 5 6 7 ← 第3层 / \ / 8 9 10 ← 第4层（最后一层从左到右连续）

下标映射关系表

数组存储示意

数组下标: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 存储内容: - A B C D E F G H I J ↑ ↑ ↑ 根节点 i=3 i=6是i=3的左子

二、堆

知识点

•堆的本质
堆是基于完全二叉树的数据结构，每个父节点的值满足特定大小关系。
•核心性质
• 堆中任意节点的子树仍是堆。
• 堆顶元素是全局极值。
•两种基本类型
•小根堆：父节点值 ≤ 子节点值，堆顶为最小值。
•大根堆：父节点值 ≥ 子节点值，堆顶为最大值。

小根堆 vs 大根堆

小根堆（父 ≤ 子，堆顶最小）：

1 ← 堆顶是最小值 / \ 3 2 / \ / \ 7 6 5 4 / 8

验证：每个父节点都小于等于子节点（1≤3,2；3≤7,6；2≤5,4；7≤8）。

大根堆（父 ≥ 子，堆顶最大）：

8 ← 堆顶是最大值 / \ 7 6 / \ / \ 3 2 5 4 / 1

验证：每个父节点都大于等于子节点（8≥7,6；7≥3,2；6≥5,4；3≥1）。

三、小根堆

知识点

•核心特征
堆顶元素始终是最小值，常用于快速获取最小元素。
•关键操作
•push：插入新元素并上浮调整。
•get：取出堆顶并下沉调整。
•上浮调整逻辑
• 新元素插入末尾。
• 不断与父节点比较交换。
• 直到满足父节点 ≤ 子节点。
•下沉调整逻辑
• 将末尾元素移到堆顶。
• 不断与较小的子节点比较交换。
• 直到满足父节点 ≤ 子节点或无子节点。

push：插入元素 2

初始状态（已有元素 {1, 3, 7, 6, 4, 8, 5}）：

1 / \ 3 4 / \ / \ 7 6 8 5

Step 1：将 2 插入到数组末尾（下标 heapSize=8）。

1 / \ 3 4 / \ / \ 7 6 8 5 / 2 ← 新插入，下标8

Step 2：比较 2 和父节点 7（下标 8/2=4），2 < 7，交换。

1 / \ 3 4 / \ / \ 2 6 8 5 ← 2 上浮到下标4 / 7 ← 7 下沉到下标8

Step 3：比较 2 和父节点 3（下标 4/2=2），2 < 3，交换。

1 / \ 2 4 ← 2 上浮到下标2 / \ / \ 3 6 8 5 ← 3 下沉到下标4 / 7

Step 4：比较 2 和父节点 1（下标 2/2=1），2 ≥ 1，停止上浮。完成。

1 / \ 2 4 / \ / \ 3 6 8 5 / 7

get：取出堆顶

Step 1：取出堆顶 1，将最后一个元素 7 放到堆顶。

7 ← 7 被移到堆顶（原来1的位置） / \ 2 4 / \ / \ 3 6 8 5

Step 2：下沉调整。比较 7 的两个子节点 2 和 4，2 更小；7 > 2，交换。

2 ← 2 上浮到堆顶 / \ 7 4 ← 7 下沉 / \ / \ 3 6 8 5

Step 3：继续比较 7 的两个子节点 3 和 6，3 更小；7 > 3，交换。

2 / \ 3 4 ← 3 上浮 / \ / \ 7 6 8 5 ← 7 下沉

Step 4：7 已经到达叶子节点（无子节点），停止下沉。完成。

示例代码

#include<bits/stdc++.h>usingnamespacestd;intheapSize;intheap[105];// 下标从 1 开始。// 插入元素 d 到小根堆中。voidpush(intd){intfa,son;// 将新元素放入数组末尾。heap[++heapSize]=d;son=heapSize;// 上浮调整：与父节点比较。while(son>1){// 计算父节点下标。fa=son/2;// 满足小根堆性质，停止上浮。if(heap[son]>=heap[fa]){break;}// 否则与父节点交换。swap(heap[fa],heap[son]);son=fa;}}// 取出小根堆的堆顶元素，最小值。intget(){// 堆为空时无法取出，返回 -1。if(heapSize==0){return-1;}// 保存堆顶元素作为返回值。intres=heap[1];// 将最后一个元素移到堆顶。heap[1]=heap[heapSize];heapSize--;intfa=1;intson=2;// 下沉调整：与较小的子节点比较。while(son<=heapSize){// 选择两个子节点中较小的那个。if(son+1<=heapSize&&heap[son+1]<heap[son]){son++;}// 满足小根堆性质，停止下沉。if(heap[fa]<=heap[son]){break;}// 否则与较小子节点交换。swap(heap[fa],heap[son]);fa=son;son=fa*2;}returnres;}

四、大根堆

知识点

•核心特征
堆顶元素始终是最大值，常用于快速获取最大元素。
•调整方向
• 上浮：子节点大于父节点时交换。
• 下沉：父节点小于子节点时交换。
•与小根堆区别
比较符号相反，其余结构与操作一致。

大根堆 vs 小根堆 核心差异对照表

示例代码

#include<bits/stdc++.h>usingnamespacestd;intheapSize;intheap[105];// 下标从 1 开始。// 插入元素 d 到大根堆中。voidpush(intd){intfa,son;// 将新元素放入数组末尾。heap[++heapSize]=d;son=heapSize;// 上浮调整：与父节点比较。while(son>1){// 计算父节点下标。fa=son/2;// 满足大根堆性质，停止上浮。if(heap[son]<=heap[fa]){break;}// 否则与父节点交换。swap(heap[fa],heap[son]);son=fa;}}// 取出大根堆的堆顶元素，最大值。intget(){// 堆为空时无法取出，返回 -1。if(heapSize==0){return-1;}// 保存堆顶元素作为返回值。intres=heap[1];// 将最后一个元素移到堆顶。heap[1]=heap[heapSize];heapSize--;intfa=1;intson=2;// 下沉调整：与较大的子节点比较。while(son<=heapSize){// 选择两个子节点中较大的那个。if(son+1<=heapSize&&heap[son+1]>heap[son]){son++;}// 满足大根堆性质，停止下沉。if(heap[fa]>=heap[son]){break;}// 否则与较大子节点交换。swap(heap[fa],heap[son]);fa=son;son=fa*2;}returnres;}

五、堆排序

知识点

•基本思想
利用堆顶元素的极值特性，反复取出堆顶得到有序序列。
•执行步骤
• 将所有元素构建成堆。
• 循环取出堆顶放入结果数组。
• 最终得到升序或降序序列。
•复杂度分析
• 建堆时间复杂度 O(n)。
• 每次调整复杂度 O(log n)。
• 总复杂度 O(n log n)。
•算法特点
堆排序是不稳定的原地排序算法。

堆排序过程

输入数组：{6, 1, 2, 3, 4}（使用小根堆实现升序排序）。

阶段一：建堆，逐个插入

插入6: [6] 插入1: [1, 6] → 1上浮：1<6，交换 插入2: [1, 6, 2] → 2上浮：2≥1，不变 插入3: [1, 3, 2, 6] → 3上浮：3<6，交换 插入4: [1, 3, 2, 6, 4] → 4上浮：4≥3，不变 最终小根堆： 1 / \ 3 2 / \ 6 4

阶段二：反复取堆顶

第1次 get → 1: 末尾4换顶 → 下沉4 → [2, 3, 4, 6] → 结果: [1] 第2次 get → 2: 末尾6换顶 → 下沉6 → [3, 6, 4] → 结果: [1, 2] 第3次 get → 3: 末尾4换顶 → 4≤6，不沉 → [4, 6] → 结果: [1, 2, 3] 第4次 get → 4: 末尾6换顶 → 不沉 → [6] → 结果: [1, 2, 3, 4] 第5次 get → 6: [] → 结果: [1, 2, 3, 4, 6]

小根堆每次取出的就是当前最小值，自然得到升序序列1 2 3 4 6，无需反转。

示例代码

// 堆排序：利用小根堆实现升序排列。voidheapSort(intarr[],intn){// 阶段一：将所有元素逐个插入小根堆建堆。for(inti=1;i<n;i++){push(arr[i]);}// 阶段二：反复取出堆顶，小根堆每次取出当前最小值，直接填入数组前部，得到升序序列。for(inti=1;i<n;i++){arr[i]=get();}}intmain(){// 下标从 1 开始存储，a[0] 不使用。inta[6]={0,6,1,2,3,4};heapSort(a,6);// 输出排序后的结果。for(inti=1;i<=5;i++){cout<<a[i]<<' ';}return0;}

六、合并果子

知识点

•问题描述
将 n 堆果子合并成一堆，每次合并两堆，消耗体力为两堆重量之和，求最小总体力消耗。
•贪心策略
每次选择最小的两堆合并，使用小根堆高效获取最小值。
•算法流程
• 所有果子入堆。
• 循环取出两个最小堆。
• 合并后放回堆中。
• 累加每次消耗的体力。
•正确性理解
先合并的堆会在后续合并中反复被累加，让小堆先合并可以把大堆的累加次数降到最低。

贪心策略正确性理解

为什么每次选最小的两堆？

假设有三堆果子：1, 2, 5 方案A（先合并最小的 1+2）： 方案B（先合并 1+5）： 第1次：1+2=3，消耗3 第1次：1+5=6，消耗6 剩余：{3, 5} 剩余：{2, 6} 第2次：3+5=8，消耗8 第2次：2+6=8，消耗8 总消耗：3+8=11 总消耗：6+8=14 结论：每次选最小的合并，总消耗最小。 因为先合并的堆会在后续合并中反复被累加， 让小堆先合并可以把大堆的累加次数降到最低。

算法执行过程

输入：n=3，果子堆为{1, 2, 9}。

初始状态： 堆内元素: [1, 2, 9]（小根堆） ans = 0 ━━━ 第1轮 ━━━ pop 最小: a = 1 pop 次小: b = 2 合并: sum = 1 + 2 = 3 push sum: 堆变为 [3, 9] ans = 0 + 3 = 3 图示： 原本三堆: ① ② ⑨ 合并①②: (①+②)=③ ⑨ 消耗体力: 3 ━━━ 第2轮 ━━━ pop 最小: a = 3 pop 次小: b = 9 合并: sum = 3 + 9 = 12 push sum: 堆变为 [12] ans = 3 + 12 = 15 图示： 剩余两堆: ③ ⑨ 合并③⑨: (③+⑨)=⑫ 消耗体力: 12 ━━━ 结束 ━━━ 只剩一堆，无法再合并。 总消耗体力: 15

示例代码

#include<bits/stdc++.h>usingnamespacestd;intheapSize;longlongheap[100005];// 小根堆：插入元素并上浮调整。voidpush(longlongd){intfa,son;// 将新元素放入数组末尾。heap[++heapSize]=d;son=heapSize;// 上浮调整：与父节点比较。while(son>1){// 计算父节点下标。fa=son/2;// 满足小根堆性质则停止上浮。if(heap[son]>=heap[fa]){break;}// 否则与父节点交换。swap(heap[fa],heap[son]);son=fa;}}// 小根堆：取出堆顶并下沉调整。longlongget(){// 堆为空时无法取出，返回 -1。if(heapSize==0){return-1;}// 保存堆顶元素作为返回值。longlongres=heap[1];// 将最后一个元素移到堆顶。heap[1]=heap[heapSize];heapSize--;intfa=1;intson=2;// 下沉调整：与较小的子节点比较。while(son<=heapSize){// 选择两个子节点中较小的那个。if(son+1<=heapSize&&heap[son+1]<heap[son]){son++;}// 满足小根堆性质则停止下沉。if(heap[fa]<=heap[son]){break;}// 否则与较小子节点交换。swap(heap[fa],heap[son]);fa=son;son=fa*2;}returnres;}intmain(){intn;// 输入果子堆数。cin>>n;// 将所有果子重量插入小根堆。for(inti=0;i<n;i++){longlongx;cin>>x;push(x);}longlongans=0;// 当堆中元素大于 1 时，继续合并。while(heapSize>1){// 取出最小的两堆。longlonga=get();longlongb=get();// 合并成新的一堆。longlongsum=a+b;// 累加体力消耗。ans+=sum;// 将合并后的堆放回。push(sum);}// 输出最小总体力消耗。cout<<ans<<"\n";return0;}

七、优先队列

知识点

•基本特性
优先队列是 C++ STL 中的容器适配器，底层通过堆实现，自动维护元素顺序，插入和删除操作时间复杂度为 O(log n)。
•大根堆（默认）
无需额外参数直接声明，队首元素始终是当前最大值。示例：priority_queue<int> pq;。
•小根堆
需指定比较规则为greater<>，队首元素始终是当前最小值。模板参数说明：priority_queue<元素类型, 底层容器, 比较规则>。
•自定义优先级
通过自定义比较函数指定优先级，适用于结构体、类或复杂排序逻辑。

自定义比较函数

• 定义一个返回bool的比较函数：bool cmp(int a, int b) { return a > b; }。
• 声明优先队列时，用函数指针把比较函数传入：priority_queue<int, vector<int>, bool(*)(int, int)> pq(cmp);。
•return a > b表示a的优先级低于b，值小的排在堆顶，实现小根堆。
• 若改成return a < b，则值大的排在堆顶，实现大根堆。

•常用成员函数
如下表所示。

示例代码

#include<iostream>#include<queue>#include<vector>#include<functional>usingnamespacestd;intmain(){// 声明大根堆，默认按降序排列。priority_queue<int>maxHeap;// 插入元素。maxHeap.push(3);maxHeap.push(10);maxHeap.push(5);// 依次输出队首元素并弹出。while(!maxHeap.empty()){cout<<maxHeap.top()<<" ";maxHeap.pop();}cout<<endl;// 声明小根堆，按升序排列。priority_queue<int,vector<int>,greater<int>>minHeap;// 插入元素。minHeap.push(3);minHeap.push(10);minHeap.push(5);// 依次输出队首元素并弹出。while(!minHeap.empty()){cout<<minHeap.top()<<" ";minHeap.pop();}return0;}

示例代码

#include<bits/stdc++.h>usingnamespacestd;// 自定义比较函数：返回 true 表示 a 的优先级低于 b。// a > b 时返回 true，即值大的优先级低，值小的排在堆顶 → 小根堆。boolcmp(inta,intb){returna>b;}intmain(){// 声明小根堆：第三个模板参数为函数指针，构造时传入比较函数 cmp。priority_queue<int,vector<int>,bool(*)(int,int)>minHeap(cmp);minHeap.push(1);minHeap.push(6);minHeap.push(3);// 依次取出队首（当前最小值）并弹出，输出：1 3 6。while(!minHeap.empty()){cout<<minHeap.top()<<" ";minHeap.pop();}return0;}

总结对照表

手写堆 vs STL 优先队列 对比

八、课程小结

1. 堆是基于完全二叉树的高效数据结构，利用数组下标映射关系实现紧凑存储。
2. 小根堆适合频繁取最小值，大根堆适合取最大值，核心区别仅在于比较符号的方向。
3. 堆排序利用堆性质实现 O(n log n) 排序，是不稳定的原地排序算法。
4. 合并果子问题是贪心算法与堆的经典应用——每次合并最小的两堆使总代价最小。
5. STL 优先队列封装了堆操作，竞赛中推荐使用，但理解底层堆原理是掌握它的前提。
6. 自定义优先队列通过自定义比较函数与函数指针实现：return a > b得小根堆，return a < b得大根堆。

知识脉络图

完全二叉树 │ ├── 数组存储（下标映射：i → 2i, 2i+1） │ ▼ 堆（父子大小关系约束） │ ├── 小根堆（父 ≤ 子，堆顶最小） │ ├── push（末尾插入 + 上浮） │ └── get（取堆顶 + 末尾换顶 + 下沉） │ ├── 大根堆（父 ≥ 子，堆顶最大） │ ├── push（末尾插入 + 上浮） │ └── get（取堆顶 + 末尾换顶 + 下沉） │ ▼ 应用场景 ├── 堆排序：反复取堆顶 → O(n log n) ├── 合并果子：贪心 + 小根堆取最小两堆 └── 优先队列：STL 封装，自定义比较函数