C++最小堆实现详解（从零开始掌握堆数据结构与优先队列）

C++ 最小堆的基本操作

一个完整的最小堆通常支持以下操作：

• insert(value)：插入新元素
• extractMin()：取出并删除堆顶最小元素
• getMin()：获取堆顶最小元素（不删除）
• heapifyUp() 和 heapifyDown()：维护堆性质

手写 C++ 最小堆实现

下面我们使用 C++ 标准库中的 vector 来实现一个最小堆类。我们将逐行解释代码逻辑。

#include <iostream>#include <vector>#include <stdexcept>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 heapifyUp(int i) {        if (i > 0 && heap[parent(i)] > heap[i]) {            swap(heap[i], heap[parent(i)]);            heapifyUp(parent(i));        }    }    // 向下调整：删除后维持堆性质    void heapifyDown(int i) {        int smallest = i;        int left = leftChild(i);        int right = rightChild(i);        if (left < heap.size() && heap[left] < heap[smallest])            smallest = left;        if (right < heap.size() && heap[right] < heap[smallest])            smallest = right;        if (smallest != i) {            swap(heap[i], heap[smallest]);            heapifyDown(smallest);        }    }public:    // 插入元素    void insert(int value) {        heap.push_back(value);        heapifyUp(heap.size() - 1);    }    // 获取最小值    int getMin() {        if (heap.empty())            throw runtime_error("Heap is empty!");        return heap[0];    }    // 弹出最小值    int extractMin() {        if (heap.empty())            throw runtime_error("Heap is empty!");        int minVal = heap[0];        heap[0] = heap.back();        heap.pop_back();        if (!heap.empty())            heapifyDown(0);        return minVal;    }    // 检查堆是否为空    bool isEmpty() {        return heap.empty();    }    // 打印堆（用于调试）    void print() {        for (int val : heap) {            cout << val << " ";        }        cout << endl;    }};

使用示例

下面是一个简单的使用示例，展示如何创建最小堆并执行基本操作：

int main() {    MinHeap minHeap;    minHeap.insert(10);    minHeap.insert(5);    minHeap.insert(20);    minHeap.insert(3);    cout << "当前最小值: " << minHeap.getMin() << endl; // 输出 3    while (!minHeap.isEmpty()) {        cout << "弹出: " << minHeap.extractMin() << endl;    }    return 0;}

为什么学习 C++ 最小堆实现很重要？

掌握 C++最小堆实现 不仅能帮助你深入理解 数据结构教程 中的核心概念，还能为面试和实际开发打下坚实基础。例如，在 LeetCode 等算法平台上，很多题目（如“合并K个升序链表”）都需要用到最小堆。

此外，C++ 标准库其实已经提供了 priority_queue，但默认是最大堆。若要使用最小堆，可以这样声明：

// 使用 greater 实现最小堆priority_queue<int, vector<int>, greater<int>> minPQ;

不过，手动实现一次最小堆，能让你真正理解其内部机制，对学习 堆排序算法 和优化程序性能大有裨益。

总结

通过本文，你已经学会了：

• 什么是最小堆及其特性
• 如何用 C++ 手动实现最小堆
• 最小堆在 C++优先队列 中的应用

建议你动手敲一遍代码，并尝试添加更多功能（如删除任意元素、构建堆等）。实践是掌握 C++最小堆实现 的最佳方式！