堆和堆排序及优先队列教学目录完全二叉树堆小根堆大根堆堆排序合并果子优先队列课程小结一、完全二叉树知识点•完全二叉树的定义除最后一层外每一层都被完全填满最后一层节点从左到右连续排列。•数组存储优势可用数组紧凑存储无需指针父子节点通过下标计算关系。•下标映射规则• 若根节点下标为 1父节点下标为i。• 左子节点下标为2*i右子节点下标为2*i1。结构示意完全二叉树的形态数字为数组下标1 ← 第1层根节点 / \ 2 3 ← 第2层 / \ / \ 4 5 6 7 ← 第3层 / \ / 8 9 10 ← 第4层最后一层从左到右连续下标映射关系表节点角色下标公式示例以节点i3为例当前节点i3父节点i / 23 / 2 1左子节点2 * i2 * 3 6右子节点2 * i 12 * 3 1 7数组存储示意数组下标: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 存储内容: - A B C D E F G H I J ↑ ↑ ↑ 根节点 i3 i6是i3的左子二、堆知识点•堆的本质堆是基于完全二叉树的数据结构每个父节点的值满足特定大小关系。•核心性质• 堆中任意节点的子树仍是堆。• 堆顶元素是全局极值。•两种基本类型•小根堆父节点值 ≤ 子节点值堆顶为最小值。•大根堆父节点值 ≥ 子节点值堆顶为最大值。小根堆 vs 大根堆小根堆父 ≤ 子堆顶最小1 ← 堆顶是最小值 / \ 3 2 / \ / \ 7 6 5 4 / 8验证每个父节点都小于等于子节点1≤3,23≤7,62≤5,47≤8。大根堆父 ≥ 子堆顶最大8 ← 堆顶是最大值 / \ 7 6 / \ / \ 3 2 5 4 / 1验证每个父节点都大于等于子节点8≥7,67≥3,26≥5,43≥1。三、小根堆知识点•核心特征堆顶元素始终是最小值常用于快速获取最小元素。•关键操作•push插入新元素并上浮调整。•get取出堆顶并下沉调整。•上浮调整逻辑• 新元素插入末尾。• 不断与父节点比较交换。• 直到满足父节点 ≤ 子节点。•下沉调整逻辑• 将末尾元素移到堆顶。• 不断与较小的子节点比较交换。• 直到满足父节点 ≤ 子节点或无子节点。push插入元素 2初始状态已有元素 {1, 3, 7, 6, 4, 8, 5}1 / \ 3 4 / \ / \ 7 6 8 5Step 1将 2 插入到数组末尾下标 heapSize8。1 / \ 3 4 / \ / \ 7 6 8 5 / 2 ← 新插入下标8Step 2比较 2 和父节点 7下标 8/242 7交换。1 / \ 3 4 / \ / \ 2 6 8 5 ← 2 上浮到下标4 / 7 ← 7 下沉到下标8Step 3比较 2 和父节点 3下标 4/222 3交换。1 / \ 2 4 ← 2 上浮到下标2 / \ / \ 3 6 8 5 ← 3 下沉到下标4 / 7Step 4比较 2 和父节点 1下标 2/212 ≥ 1停止上浮。完成。1 / \ 2 4 / \ / \ 3 6 8 5 / 7get取出堆顶Step 1取出堆顶 1将最后一个元素 7 放到堆顶。7 ← 7 被移到堆顶原来1的位置 / \ 2 4 / \ / \ 3 6 8 5Step 2下沉调整。比较 7 的两个子节点 2 和 42 更小7 2交换。2 ← 2 上浮到堆顶 / \ 7 4 ← 7 下沉 / \ / \ 3 6 8 5Step 3继续比较 7 的两个子节点 3 和 63 更小7 3交换。2 / \ 3 4 ← 3 上浮 / \ / \ 7 6 8 5 ← 7 下沉Step 47 已经到达叶子节点无子节点停止下沉。完成。示例代码#includebits/stdc.husingnamespacestd;intheapSize;intheap[105];// 下标从 1 开始。// 插入元素 d 到小根堆中。voidpush(intd){intfa,son;// 将新元素放入数组末尾。heap[heapSize]d;sonheapSize;// 上浮调整与父节点比较。while(son1){// 计算父节点下标。fason/2;// 满足小根堆性质停止上浮。if(heap[son]heap[fa]){break;}// 否则与父节点交换。swap(heap[fa],heap[son]);sonfa;}}// 取出小根堆的堆顶元素最小值。intget(){// 堆为空时无法取出返回 -1。if(heapSize0){return-1;}// 保存堆顶元素作为返回值。intresheap[1];// 将最后一个元素移到堆顶。heap[1]heap[heapSize];heapSize--;intfa1;intson2;// 下沉调整与较小的子节点比较。while(sonheapSize){// 选择两个子节点中较小的那个。if(son1heapSizeheap[son1]heap[son]){son;}// 满足小根堆性质停止下沉。if(heap[fa]heap[son]){break;}// 否则与较小子节点交换。swap(heap[fa],heap[son]);fason;sonfa*2;}returnres;}四、大根堆知识点•核心特征堆顶元素始终是最大值常用于快速获取最大元素。•调整方向• 上浮子节点大于父节点时交换。• 下沉父节点小于子节点时交换。•与小根堆区别比较符号相反其余结构与操作一致。大根堆 vs 小根堆 核心差异对照表操作小根堆大根堆堆顶含义最小值最大值上浮条件heap[son] heap[fa]heap[son] heap[fa]下沉选子选较小的子节点选较大的子节点下沉停止heap[fa] heap[son]heap[fa] heap[son]示例代码#includebits/stdc.husingnamespacestd;intheapSize;intheap[105];// 下标从 1 开始。// 插入元素 d 到大根堆中。voidpush(intd){intfa,son;// 将新元素放入数组末尾。heap[heapSize]d;sonheapSize;// 上浮调整与父节点比较。while(son1){// 计算父节点下标。fason/2;// 满足大根堆性质停止上浮。if(heap[son]heap[fa]){break;}// 否则与父节点交换。swap(heap[fa],heap[son]);sonfa;}}// 取出大根堆的堆顶元素最大值。intget(){// 堆为空时无法取出返回 -1。if(heapSize0){return-1;}// 保存堆顶元素作为返回值。intresheap[1];// 将最后一个元素移到堆顶。heap[1]heap[heapSize];heapSize--;intfa1;intson2;// 下沉调整与较大的子节点比较。while(sonheapSize){// 选择两个子节点中较大的那个。if(son1heapSizeheap[son1]heap[son]){son;}// 满足大根堆性质停止下沉。if(heap[fa]heap[son]){break;}// 否则与较大子节点交换。swap(heap[fa],heap[son]);fason;sonfa*2;}returnres;}五、堆排序知识点•基本思想利用堆顶元素的极值特性反复取出堆顶得到有序序列。•执行步骤• 将所有元素构建成堆。• 循环取出堆顶放入结果数组。• 最终得到升序或降序序列。•复杂度分析• 建堆时间复杂度 O(n)。• 每次调整复杂度 O(log n)。• 总复杂度 O(n log n)。•算法特点堆排序是不稳定的原地排序算法。堆排序过程输入数组{6, 1, 2, 3, 4}使用小根堆实现升序排序。阶段一建堆逐个插入插入6: [6] 插入1: [1, 6] → 1上浮16交换 插入2: [1, 6, 2] → 2上浮2≥1不变 插入3: [1, 3, 2, 6] → 3上浮36交换 插入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(inti1;in;i){push(arr[i]);}// 阶段二反复取出堆顶小根堆每次取出当前最小值直接填入数组前部得到升序序列。for(inti1;in;i){arr[i]get();}}intmain(){// 下标从 1 开始存储a[0] 不使用。inta[6]{0,6,1,2,3,4};heapSort(a,6);// 输出排序后的结果。for(inti1;i5;i){couta[i] ;}return0;}六、合并果子知识点•问题描述将 n 堆果子合并成一堆每次合并两堆消耗体力为两堆重量之和求最小总体力消耗。•贪心策略每次选择最小的两堆合并使用小根堆高效获取最小值。•算法流程• 所有果子入堆。• 循环取出两个最小堆。• 合并后放回堆中。• 累加每次消耗的体力。•正确性理解先合并的堆会在后续合并中反复被累加让小堆先合并可以把大堆的累加次数降到最低。贪心策略正确性理解为什么每次选最小的两堆假设有三堆果子1, 2, 5 方案A先合并最小的 12 方案B先合并 15 第1次123消耗3 第1次156消耗6 剩余{3, 5} 剩余{2, 6} 第2次358消耗8 第2次268消耗8 总消耗3811 总消耗6814 结论每次选最小的合并总消耗最小。 因为先合并的堆会在后续合并中反复被累加 让小堆先合并可以把大堆的累加次数降到最低。算法执行过程输入n3果子堆为{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示例代码#includebits/stdc.husingnamespacestd;intheapSize;longlongheap[100005];// 小根堆插入元素并上浮调整。voidpush(longlongd){intfa,son;// 将新元素放入数组末尾。heap[heapSize]d;sonheapSize;// 上浮调整与父节点比较。while(son1){// 计算父节点下标。fason/2;// 满足小根堆性质则停止上浮。if(heap[son]heap[fa]){break;}// 否则与父节点交换。swap(heap[fa],heap[son]);sonfa;}}// 小根堆取出堆顶并下沉调整。longlongget(){// 堆为空时无法取出返回 -1。if(heapSize0){return-1;}// 保存堆顶元素作为返回值。longlongresheap[1];// 将最后一个元素移到堆顶。heap[1]heap[heapSize];heapSize--;intfa1;intson2;// 下沉调整与较小的子节点比较。while(sonheapSize){// 选择两个子节点中较小的那个。if(son1heapSizeheap[son1]heap[son]){son;}// 满足小根堆性质则停止下沉。if(heap[fa]heap[son]){break;}// 否则与较小子节点交换。swap(heap[fa],heap[son]);fason;sonfa*2;}returnres;}intmain(){intn;// 输入果子堆数。cinn;// 将所有果子重量插入小根堆。for(inti0;in;i){longlongx;cinx;push(x);}longlongans0;// 当堆中元素大于 1 时继续合并。while(heapSize1){// 取出最小的两堆。longlongaget();longlongbget();// 合并成新的一堆。longlongsumab;// 累加体力消耗。anssum;// 将合并后的堆放回。push(sum);}// 输出最小总体力消耗。coutans\n;return0;}七、优先队列知识点•基本特性优先队列是 C STL 中的容器适配器底层通过堆实现自动维护元素顺序插入和删除操作时间复杂度为 O(log n)。•大根堆默认无需额外参数直接声明队首元素始终是当前最大值。示例priority_queueint pq;。•小根堆需指定比较规则为greater队首元素始终是当前最小值。模板参数说明priority_queue元素类型, 底层容器, 比较规则。•自定义优先级通过自定义比较函数指定优先级适用于结构体、类或复杂排序逻辑。自定义比较函数• 定义一个返回bool的比较函数bool cmp(int a, int b) { return a b; }。• 声明优先队列时用函数指针把比较函数传入priority_queueint, vectorint, bool(*)(int, int) pq(cmp);。•return a b表示a的优先级低于b值小的排在堆顶实现小根堆。• 若改成return a b则值大的排在堆顶实现大根堆。•常用成员函数如下表所示。函数作用push()插入元素到优先队列。pop()删除队首元素。top()访问队首元素。empty()判断优先队列是否为空。size()返回优先队列中元素个数。示例代码#includeiostream#includequeue#includevector#includefunctionalusingnamespacestd;intmain(){// 声明大根堆默认按降序排列。priority_queueintmaxHeap;// 插入元素。maxHeap.push(3);maxHeap.push(10);maxHeap.push(5);// 依次输出队首元素并弹出。while(!maxHeap.empty()){coutmaxHeap.top() ;maxHeap.pop();}coutendl;// 声明小根堆按升序排列。priority_queueint,vectorint,greaterintminHeap;// 插入元素。minHeap.push(3);minHeap.push(10);minHeap.push(5);// 依次输出队首元素并弹出。while(!minHeap.empty()){coutminHeap.top() ;minHeap.pop();}return0;}示例代码#includebits/stdc.husingnamespacestd;// 自定义比较函数返回 true 表示 a 的优先级低于 b。// a b 时返回 true即值大的优先级低值小的排在堆顶 → 小根堆。boolcmp(inta,intb){returnab;}intmain(){// 声明小根堆第三个模板参数为函数指针构造时传入比较函数 cmp。priority_queueint,vectorint,bool(*)(int,int)minHeap(cmp);minHeap.push(1);minHeap.push(6);minHeap.push(3);// 依次取出队首当前最小值并弹出输出1 3 6。while(!minHeap.empty()){coutminHeap.top() ;minHeap.pop();}return0;}总结对照表类型写法大根堆priority_queueint小根堆priority_queueint, vectorint, greaterint 自定义优先级priority_queueint, vectorint, bool(*)(int, int) pq(cmp)手写堆 vs STL 优先队列 对比维度手写堆STL priority_queue代码量较多约 30 行极少1 行声明性能略优无模板开销优秀灵活性可自由修改内部逻辑受限于 STL 接口调试难度容易调试黑盒不易调试删除任意元素可实现不支持遍历元素可直接访问数组不支持竞赛建议学习原理时使用熟练后优先使用八、课程小结堆是基于完全二叉树的高效数据结构利用数组下标映射关系实现紧凑存储。小根堆适合频繁取最小值大根堆适合取最大值核心区别仅在于比较符号的方向。堆排序利用堆性质实现 O(n log n) 排序是不稳定的原地排序算法。合并果子问题是贪心算法与堆的经典应用——每次合并最小的两堆使总代价最小。STL 优先队列封装了堆操作竞赛中推荐使用但理解底层堆原理是掌握它的前提。自定义优先队列通过自定义比较函数与函数指针实现return a b得小根堆return a b得大根堆。知识脉络图完全二叉树 │ ├── 数组存储下标映射i → 2i, 2i1 │ ▼ 堆父子大小关系约束 │ ├── 小根堆父 ≤ 子堆顶最小 │ ├── push末尾插入 上浮 │ └── get取堆顶 末尾换顶 下沉 │ ├── 大根堆父 ≥ 子堆顶最大 │ ├── push末尾插入 上浮 │ └── get取堆顶 末尾换顶 下沉 │ ▼ 应用场景 ├── 堆排序反复取堆顶 → O(n log n) ├── 合并果子贪心 小根堆取最小两堆 └── 优先队列STL 封装自定义比较函数