【堆与优先队列】堆与优先队列：“数据金字塔“与“我是 VIP“
作者：华为云开发者联盟
- 2025-10-20 中国香港
本文字数：10957 字
阅读完需：约 36 分钟
一、概述
1. 案例介绍
堆（Heap）和 优先队列（Priority Queue）是紧密相关的数据结构，都用于高效地管理元素并根据优先级（通常是最大值或最小值）进行访问。优先队列通常使用堆来实现。案例会介绍堆和优先队列的基本概念、常用方法，最终使用堆和优先队列完成一个简单的系统开发。本案例相关实验将在华为云开发者空间云主机进行，开发者空间云主机为开发者提供了高效稳定的云资源，确保用户的数据安全。云主机当前已适配完整的 C/C++开发环境，支持 VS Code 等多种 IDE 工具安装调测。
2. 适用对象
个人开发者
高校学生
3. 案例时间
本案例总时长预计 60 分钟。
4. 案例流程
说明：
开通开发者空间，搭建 C/C++开发环境；
打开 VS Code，编写代码运行程序。
资源总览
本案例预计花费 0 元。
最新案例动态，请查阅 《【堆与优先队列】“数据金字塔”与“我是VIP”》。小伙伴快来领取华为开发者空间进行实操吧！
二、配置实验环境
1. 开发者空间配置
面向广大开发者群体，华为开发者空间提供一个随时访问的“开发桌面云主机”、丰富的“预配置工具集合”和灵活使用的“场景化资源池”，开发者开箱即用，快速体验华为根技术和资源。
如果还没有领取开发者空间云主机，可以参考免费领取云主机文档领取。
领取云主机后可以直接进入华为开发者空间工作台界面，点击打开云主机 > 进入桌面连接云主机。
2. 配置实验环境
参考案例中心《基于开发者空间，定制C&C++开发环境云主机镜像》“2. 实验环境搭建”、“3. VS Code 安装部署”章节完成开发环境、VS Code 及插件安装。
三、堆和优先队列的基本操作
1. 基本概念
堆（Heap）是一种特殊的完全二叉树，可以简洁地使用数组表示和维护。堆适合于需要维护最值的场景，它满足父节点的值总是不大于或不小于其子节点的值。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
优先级队列（PriorityQueue）是 0 个或多个元素的集合，每个元素都有一个优先权；对优先级队列执行的操作有查找、插入、删除。一般情况下，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。
2. 堆的操作
1）堆的插入（Insert / Push / Offer）：
将新元素添加到数组末尾（堆的最后一个叶子节点位置）。
上浮 (Percolate Up / Sift Up / Swim): 比较新节点与其父节点的值。最大堆：如果新节点值 > 父节点值，则交换它们的位置。最小堆：如果新节点值 < 父节点值，则交换它们的位置。
重复步骤上浮，直到新节点找到合适的位置（满足堆序性），或者到达根节点。
时间复杂度：O(log n) (树的高度)。
下面我们实现一个最小堆的插入操作，代码如下：
#include <iostream>#include <vector>#include <algorithm>using namespace std;class MinHeap {private: vector<int> heap; // 上浮调整（从当前节点向根节点调整） void siftUp(int index) { while (index > 0) { // 计算父节点索引 int parentIndex = (index - 1) / 2; if (heap[parentIndex] <= heap[index]) break; // 如果父节点更小，满足最小堆性质 // 交换父子节点 swap(heap[parentIndex], heap[index]); // 继续向上检查 index = parentIndex; } }
public: // 插入新元素 void insert(int value) { // 1. 将新元素添加到堆末尾 heap.push_back(value); // 2. 从新元素位置进行上浮调整 siftUp(heap.size() - 1); }
// 打印堆内容（辅助函数） void printHeap() { for (int val : heap) cout << val << " "; cout << endl; }};
int main() { MinHeap heap; // 插入示例 heap.insert(10); heap.insert(5); heap.insert(15); heap.insert(2); heap.insert(7); cout << "最小堆内容: "; heap.printHeap(); // 输出应为：2 5 15 10 7 return 0;}
复制代码
点击编辑器左上角运行按钮直接运行。
输出内容截图如下：
2）堆排序 (Heap Sort):堆排序是一种高效的比较类排序算法，时间复杂度为 O(n log n)，并且具有原地排序（空间复杂度 O(1)）的优点。下面我将实现一个完整的堆排序程序。关键函数：heapify。
void heapify(vector<int>& arr, int n, int i) { int largest = i; // 初始化最大元素为根节点 int left = 2 * i + 1; // 左子节点 int right = 2 * i + 2; // 右子节点
// 比较左子节点 if (left < n && arr[left] > arr[largest]) largest = left;
// 比较右子节点 if (right < n && arr[right] > arr[largest]) largest = right;
// 如果最大值不是根节点 if (largest != i) { swap(arr[i], arr[largest]); // 交换 heapify(arr, n, largest); // 递归调整子树 }}
复制代码
完整代码如下：
#include <iostream>#include <vector>#include <algorithm>using namespace std;
// 堆调整函数（大顶堆）void heapify(vector<int>& arr, int n, int i) { int largest = i; // 初始化最大元素为根节点 int left = 2 * i + 1; // 左子节点 int right = 2 * i + 2; // 右子节点
// 如果左子节点存在且大于根节点 if (left < n && arr[left] > arr[largest]) largest = left;
// 如果右子节点存在且大于当前最大值 if (right < n && arr[right] > arr[largest]) largest = right;
// 如果最大值不是根节点 if (largest != i) { swap(arr[i], arr[largest]); // 交换 heapify(arr, n, largest); // 递归调整子树 }}
// 堆排序主函数void heapSort(vector<int>& arr) { int n = arr.size(); // 1. 构建大顶堆（从最后一个非叶子节点开始） for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // 2. 逐个提取元素（交换堆顶和末尾元素，然后调整堆） for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); // 将当前最大值移到数组末尾 heapify(arr, i, 0); // 调整剩余元素组成的堆 }}
// 打印数组void printArray(const vector<int>& arr) { for (int num : arr) cout << num << " "; cout << endl;}
int main() { vector<int> arr = {12, 11, 13, 5, 6, 7, 20, 1, 8}; cout << "排序前数组: "; printArray(arr); heapSort(arr); cout << "堆排序后数组: "; printArray(arr); // 测试不同情况 vector<int> empty = {}; vector<int> single = {5}; vector<int> sorted = {1, 2, 3, 4, 5}; vector<int> reverse = {9, 8, 7, 6, 5}; vector<int> duplicates = {3, 1, 4, 1, 5, 9, 2, 6, 5}; cout << "\n测试空数组: "; heapSort(empty); printArray(empty); cout << "测试单元素数组: "; heapSort(single); printArray(single); cout << "测试已排序数组: "; heapSort(sorted); printArray(sorted); cout << "测试逆序数组: "; heapSort(reverse); printArray(reverse); cout << "测试重复元素数组: "; heapSort(duplicates); printArray(duplicates); return 0;}
复制代码
点击编辑器左上角运行按钮直接运行。
输出内容截图如下：
3）删除堆顶元素 (DeleteMax / DeleteMin / Poll):
移除根节点元素（即数组的第一个元素）。
将数组的最后一个元素（最后一个叶子节点）移动到根节点位置。
下沉 (Percolate Down / Sift Down / Heapify / Sink): 比较新的根节点与其较大的（最大堆）或较小的（最小堆）子节点的值。
重复下沉，直到该节点找到合适的位置（满足堆序性），或者到达叶子节点。
时间复杂度：O(log n) (树的高度)。
删除代码样例如下，代码中添加了详细的输出信息，帮助理解求解过程：
#include <iostream>#include <vector>#include <algorithm>using namespace std;
class MinHeap {private: vector<int> heap;
// 获取父节点索引 int parent(int i) { return (i - 1) / 2; }
// 获取左子节点索引 int leftChild(int i) { return 2 * i + 1; }
// 获取右子节点索引 int rightChild(int i) { return 2 * i + 2; }
// 从指定位置开始向下调整堆 void heapifyDown(int i) { int smallest = i; // 初始化最小值位置 int left = leftChild(i); // 左子节点索引 int right = rightChild(i); // 右子节点索引 int size = heap.size();
// 与左子节点比较 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]); heapifyDown(smallest); // 递归调整子树 } }
public: // 删除堆顶元素 void deleteTop() { if (heap.empty()) { cerr << "Heap is empty!" << endl; return; }
// 将最后一个元素移到堆顶 heap[0] = heap.back(); heap.pop_back();
// 从根节点开始向下调整 heapifyDown(0); }
// 插入元素 void insert(int value) { heap.push_back(value); // 添加到末尾 int i = heap.size() - 1;
// 向上调整 while (i != 0 && heap[i] < heap[parent(i)]) { swap(heap[i], heap[parent(i)]); i = parent(i); } }
// 获取堆顶元素 int getTop() { if (heap.empty()) { cerr << "Heap is empty!" << endl; return -1; // 返回错误值 } return heap[0]; }
// 打印堆 void printHeap() { for (int val : heap) cout << val << " "; cout << endl; }};
int main() { MinHeap heap;
// 构建堆 [5, 3, 8, 1, 2] heap.insert(5); heap.insert(3); heap.insert(8); heap.insert(1); heap.insert(2);
cout << "初始堆: "; heap.printHeap(); // 输出: 1 2 8 5 3（实际结构可能不同）
// 删除堆顶 heap.deleteTop(); cout << "删除堆顶后: "; heap.printHeap(); // 输出: 2 3 8 5（堆结构）
// 再删除一次 heap.deleteTop(); cout << "再删除堆顶后: "; heap.printHeap(); // 输出: 3 5 8（堆结构）
return 0;}
复制代码
输出内容截图如下：
3. 优先队列的操作
1）优先队列的入队和出队（Enqueue / Push / Offer & Dequeue / Pop / Poll）：我们以 push 做入队操作，以 pop 做出队操作，分别以最大堆和最小堆实现优先队列的入队和出队。代码如下：
#include <iostream>#include <queue>#include <vector>#include <functional> // 用于greater<int>using namespace std;
int main() { cout << "========== C++优先级队列操作演示 ==========\n" << endl; // 案例1: 最大堆（默认）的入队和出队操作 cout << "案例1: 最大堆操作" << endl; priority_queue<int> maxHeap; // 入队操作 cout << "入队操作: 添加元素 30, 10, 50, 20, 40" << endl; maxHeap.push(30); maxHeap.push(10); maxHeap.push(50); maxHeap.push(20); maxHeap.push(40); cout << "当前队列内容: "; while (!maxHeap.empty()) { cout << maxHeap.top() << " "; // 查看队首元素 maxHeap.pop(); // 出队操作 } cout << "\n(注意: 元素从大到小出队)\n" << endl; // 案例2: 最小堆的入队和出队操作 cout << "案例2: 最小堆操作" << endl; priority_queue<int, vector<int>, greater<int>> minHeap; // 入队操作 cout << "入队操作: 添加元素 30, 10, 50, 20, 40" << endl; minHeap.push(30); minHeap.push(10); minHeap.push(50); minHeap.push(20); minHeap.push(40); cout << "当前队列内容: "; while (!minHeap.empty()) { cout << minHeap.top() << " "; // 查看队首元素 minHeap.pop(); // 出队操作 } cout << "\n(注意: 元素从小到大出队)\n" << endl; return 0;}
复制代码
输出内容截图：
2）优先队列的判空和获取大小（empty() & size()）：我们分别以最大堆和最小堆实现判空操作获取大小。代码如下：
#include <iostream>#include <queue>#include <vector>#include <functional>using namespace std;
int main() { cout << "====优先级队列判空与大小操作 ====\n" << endl; //判空操作演示 cout << "判空操作" << endl; // 创建一个空的最大堆 priority_queue<int> maxHeap; // 检查队列是否为空 cout << "初始队列是否为空? " << (maxHeap.empty() ? "是" : "否") << endl; // 添加一些元素 cout << "\n添加三个元素: 50, 30, 40" << endl; maxHeap.push(50); maxHeap.push(30); maxHeap.push(40); // 再次检查队列是否为空 cout << "添加元素后队列是否为空? " << (maxHeap.empty() ? "是" : "否") << endl; // 清空队列 cout << "\n清空队列..." << endl; while (!maxHeap.empty()) { maxHeap.pop(); } // 最终检查队列是否为空 cout << "清空后队列是否为空? " << (maxHeap.empty() ? "是" : "否") << endl; cout << "-----------------------------\n" << endl; // 获取队列大小操作 cout << "获取队列大小" << endl; // 创建一个最小堆 priority_queue<int, vector<int>, greater<int>> minHeap; // 初始大小 cout << "初始队列大小: " << minHeap.size() << endl; // 添加元素并显示大小变化 cout << "\n添加元素: 10" << endl; minHeap.push(10); cout << "当前队列大小: " << minHeap.size() << endl; cout << "添加元素: 20" << endl; minHeap.push(20); cout << "当前队列大小: " << minHeap.size() << endl; // 移除元素并显示大小变化 cout << "\n移除一个元素..." << endl; minHeap.pop(); cout << "当前队列大小: " << minHeap.size() << endl; cout << "再移除一个元素..." << endl; minHeap.pop(); cout << "当前队列大小: " << minHeap.size() << endl; // 尝试在空队列上操作 cout << "\n尝试在空队列上移除元素..." << endl; if (!minHeap.empty()) { minHeap.pop(); } else { cout << "队列为空，无法执行pop操作" << endl; } cout << "----------------------------------------\n" << endl; return 0;}
复制代码
输出内容文本显示：
====优先级队列判空与大小操作 ====
判空操作初始队列是否为空? 是
添加三个元素: 50, 30, 40添加元素后队列是否为空? 否
清空队列...清空后队列是否为空? 是-----------------------------
获取队列大小初始队列大小: 0
添加元素: 10当前队列大小: 1添加元素: 20当前队列大小: 2
移除一个元素...当前队列大小: 1再移除一个元素...当前队列大小: 0
尝试在空队列上移除元素...队列为空，无法执行pop操作----------------------------------------
复制代码
四、医院急诊分诊系统
下面我将使用堆（手动实现）和优先队列（STL）分别实现一个医院急诊分诊系统。该系统根据病情的严重程度对患者进行优先级排序，确保最危急的患者最先得到治疗。
#include <iostream>#include <vector>#include <queue>#include <ctime>#include <iomanip>#include <thread> #include <chrono> using namespace std;
//患者结构体struct Patient { string name; // 病情严重程度：1-危重(最高) 2-紧急 3-中度 4-轻度(最低) int severity; // 到达时间 time_t arrivalTime; Patient(string n, int s) : name(n), severity(s) { // 记录到达时间 arrivalTime = time(nullptr); } // 重载比较运算符（用于STL优先队列） bool operator<(const Patient& other) const { // 优先比较严重程度（数值越小越严重） if (severity != other.severity) { // 注意：优先队列默认最大堆，所以反转比较 return severity > other.severity; } // 严重程度相同时，比较到达时间（先到先服务） return arrivalTime > other.arrivalTime; }};
// 手动实现的堆（最小堆）class MinHeap {private: vector<Patient> heap; // 获取父节点索引 int parent(int i) { return (i - 1) / 2; } // 获取左子节点索引 int leftChild(int i) { return 2 * i + 1; } // 获取右子节点索引 int rightChild(int i) { return 2 * i + 2; } // 堆化向上调整 void heapifyUp(int i) { while (i > 0) { int p = parent(i); // 比较严重程度 if (heap[p].severity > heap[i].severity || (heap[p].severity == heap[i].severity && heap[p].arrivalTime > heap[i].arrivalTime)) { swap(heap[p], heap[i]); i = p; } else { break; } } } // 堆化向下调整 void heapifyDown(int i) { int smallest = i; int left = leftChild(i); int right = rightChild(i); int size = heap.size(); // 找出最紧急的患者（严重程度最小，相同则最早到达） if (left < size) { if (heap[left].severity < heap[smallest].severity || (heap[left].severity == heap[smallest].severity && heap[left].arrivalTime < heap[smallest].arrivalTime)) { smallest = left; } } if (right < size) { if (heap[right].severity < heap[smallest].severity || (heap[right].severity == heap[smallest].severity && heap[right].arrivalTime < heap[smallest].arrivalTime)) { smallest = right; } } // 如果需要交换，则递归调整 if (smallest != i) { swap(heap[i], heap[smallest]); heapifyDown(smallest); } }
public: // 添加患者 void addPatient(const Patient& p) { heap.push_back(p); heapifyUp(heap.size() - 1); } // 治疗下一个患者 Patient treatNext() { if (heap.empty()) { throw runtime_error("没有患者等待治疗"); } Patient next = heap[0]; heap[0] = heap.back(); heap.pop_back(); if (!heap.empty()) { heapifyDown(0); } return next; } // 查看下一个患者 Patient peekNext() const { if (heap.empty()) { throw runtime_error("没有患者等待治疗"); } return heap[0]; } // 检查是否为空 bool isEmpty() const { return heap.empty(); } // 获取等待患者数量 int patientCount() const { return heap.size(); } // 打印当前等待患者 void printQueue() const { if (heap.empty()) { cout << "当前没有患者等待" << endl; return; } cout << "当前等待患者 (" << heap.size() << "人):" << endl; cout << "==========================================" << endl; cout << left << setw(15) << "姓名" << setw(10) << "严重程度" << "到达时间" << endl; cout << "------------------------------------------" << endl; for (const auto& p : heap) { cout << left << setw(15) << p.name; cout << setw(10); switch (p.severity) { case 1: cout << "危重"; break; case 2: cout << "紧急"; break; case 3: cout << "中度"; break; case 4: cout << "轻度"; break; } // 修正时间显示 cout << ctime(&p.arrivalTime); } cout << "==========================================" << endl; }};
// 打印时间差（用于显示等待时间）void printWaitTime(time_t arrival) { time_t now = time(nullptr); double diff = difftime(now, arrival); int minutes = static_cast<int>(diff) / 60; cout << "(等待时间: " << minutes << "分钟)";}
int main() { cout << "========== 医院急诊分诊系统 ==========\n" << endl; cout << "病情严重程度定义:\n"; cout << "1-危重(最高) 2-紧急 3-中度 4-轻度(最低)\n" << endl; // 使用手动实现的堆 cout << "===== 使用手动实现的堆 =====" << endl; MinHeap heapTriage; // 添加患者 heapTriage.addPatient(Patient("张三", 3)); // 中度 heapTriage.addPatient(Patient("李四", 1)); // 危重 heapTriage.addPatient(Patient("王五", 2)); // 紧急 heapTriage.addPatient(Patient("赵六", 4)); // 轻度 heapTriage.addPatient(Patient("钱七", 1)); // 危重 heapTriage.addPatient(Patient("孙八", 3)); // 中度 // 显示当前队列 heapTriage.printQueue(); // 治疗患者 cout << "\n开始治疗患者..." << endl; while (!heapTriage.isEmpty()) { Patient next = heapTriage.peekNext(); cout << "治疗: " << next.name << " [严重程度: "; switch (next.severity) { case 1: cout << "危重"; break; case 2: cout << "紧急"; break; case 3: cout << "中度"; break; case 4: cout << "轻度"; break; } cout << "] "; printWaitTime(next.arrivalTime); cout << endl; heapTriage.treatNext(); // 治疗该患者 // 模拟治疗间隔 - 使用正确的命名空间 this_thread::sleep_for(chrono::seconds(1)); } // 使用STL优先队列 cout << "\n\n===== 使用STL优先队列 =====" << endl; priority_queue<Patient> pqTriage; // 添加患者 pqTriage.push(Patient("张三", 3)); // 中度 pqTriage.push(Patient("李四", 1)); // 危重 pqTriage.push(Patient("王五", 2)); // 紧急 pqTriage.push(Patient("赵六", 4)); // 轻度 pqTriage.push(Patient("钱七", 1)); // 危重 pqTriage.push(Patient("孙八", 3)); // 中度 // 治疗患者 cout << "\n开始治疗患者..." << endl; while (!pqTriage.empty()) { Patient next = pqTriage.top(); cout << "治疗: " << next.name << " [严重程度: "; switch (next.severity) { case 1: cout << "危重"; break; case 2: cout << "紧急"; break; case 3: cout << "中度"; break; case 4: cout << "轻度"; break; } cout << "] "; printWaitTime(next.arrivalTime); cout << endl; pqTriage.pop(); // 治疗该患者 // 模拟治疗间隔 - 使用正确的命名空间 this_thread::sleep_for(chrono::seconds(1)); } cout << "\n所有患者治疗完成!" << endl; cout << "================================" << endl; return 0;}
复制代码
输出内容文本显示：
========== 医院急诊分诊系统 ==========
病情严重程度定义:1-危重(最高) 2-紧急 3-中度 4-轻度(最低)
===== 使用手动实现的堆 =====当前等待患者 (6人):==========================================姓名 严重程度到达时间------------------------------------------李四 危重 Thu Jun 26 11:06:25 2025钱七 危重 Thu Jun 26 11:06:25 2025王五 紧急 Thu Jun 26 11:06:25 2025赵六 轻度 Thu Jun 26 11:06:25 2025张三 中度 Thu Jun 26 11:06:25 2025孙八 中度 Thu Jun 26 11:06:25 2025==========================================
开始治疗患者...治疗: 李四 [严重程度: 危重] (等待时间: 0分钟)治疗: 钱七 [严重程度: 危重] (等待时间: 0分钟)治疗: 王五 [严重程度: 紧急] (等待时间: 0分钟)治疗: 孙八 [严重程度: 中度] (等待时间: 0分钟)治疗: 张三 [严重程度: 中度] (等待时间: 0分钟)治疗: 赵六 [严重程度: 轻度] (等待时间: 0分钟)
===== 使用STL优先队列 =====
开始治疗患者...治疗: 李四 [严重程度: 危重] (等待时间: 0分钟)治疗: 钱七 [严重程度: 危重] (等待时间: 0分钟)治疗: 王五 [严重程度: 紧急] (等待时间: 0分钟)治疗: 孙八 [严重程度: 中度] (等待时间: 0分钟)治疗: 张三 [严重程度: 中度] (等待时间: 0分钟)治疗: 赵六 [严重程度: 轻度] (等待时间: 0分钟)
所有患者治疗完成!================================
复制代码
至此，【堆与优先队列】“数据金字塔”与“我是 VIP”案例已全部完成。
划线
评论
复制
发布于: 刚刚阅读数: 5
华为云开发者联盟
关注
提供全面深入的云计算技术干货 2020-07-14 加入
生于云，长于云，让开发者成为决定性力量
评论