C++堆数据结构详解（从零开始手把手教你实现堆）

什么是堆？

堆是一种完全二叉树，分为两种类型：

• 最大堆（Max Heap）：父节点的值总是大于或等于其子节点的值。
• 最小堆（Min Heap）：父节点的值总是小于或等于其子节点的值。

由于堆是完全二叉树，我们可以使用数组来高效地存储它，而不需要复杂的指针结构。这也是为什么C++堆数据结构在实际开发中非常受欢迎的原因之一。

堆的基本操作

堆通常支持以下核心操作：

• insert(value)：插入一个新元素。
• extract()：取出堆顶元素（最大值或最小值）。
• peek()：查看堆顶元素但不删除。
• heapifyUp() 和 heapifyDown()：维护堆的性质。

C++实现最小堆

下面我们用 C++ 实现一个最小堆。我们将使用 std::vector 来存储堆中的元素。

#include <iostream>#include <vector>class MinHeap {private:    std::vector<int> heap;    // 获取父节点、左子节点、右子节点的索引    int parent(int i) { return (i - 1) / 2; }    int left(int i) { return 2 * i + 1; }    int right(int i) { return 2 * i + 2; }    // 向上调整（插入后使用）    void heapifyUp(int i) {        while (i != 0 && heap[parent(i)] > heap[i]) {            std::swap(heap[i], heap[parent(i)]);            i = parent(i);        }    }    // 向下调整（删除后使用）    void heapifyDown(int i) {        int smallest = i;        int l = left(i);        int r = right(i);        if (l < heap.size() && heap[l] < heap[smallest])            smallest = l;        if (r < heap.size() && heap[r] < heap[smallest])            smallest = r;        if (smallest != i) {            std::swap(heap[i], heap[smallest]);            heapifyDown(smallest);        }    }public:    // 插入元素    void insert(int value) {        heap.push_back(value);        heapifyUp(heap.size() - 1);    }    // 获取堆顶元素    int peek() {        if (heap.empty()) {            throw std::runtime_error("Heap is empty!");        }        return heap[0];    }    // 弹出堆顶元素    int extract() {        if (heap.empty()) {            throw std::runtime_error("Heap is empty!");        }        int root = heap[0];        heap[0] = heap.back();        heap.pop_back();        if (!heap.empty()) {            heapifyDown(0);        }        return root;    }    // 检查堆是否为空    bool isEmpty() {        return heap.empty();    }    // 打印堆（用于调试）    void print() {        for (int val : heap) {            std::cout << val << " ";        }        std::cout << std::endl;    }};

使用示例

下面是一个简单的使用示例：

int main() {    MinHeap minHeap;    minHeap.insert(10);    minHeap.insert(5);    minHeap.insert(20);    minHeap.insert(3);    std::cout << "堆顶元素: " << minHeap.peek() << std::endl; // 输出 3    while (!minHeap.isEmpty()) {        std::cout << minHeap.extract() << " "; // 依次输出 3 5 10 20    }    return 0;}

为什么学习堆很重要？

掌握堆的实现对于理解高级算法（如 Dijkstra 最短路径、堆排序等）至关重要。此外，C++ 标准库中的 std::priority_queue 就是基于堆实现的，因此理解底层原理有助于你更高效地使用它。

通过本教程，你已经学会了如何从零构建一个最小堆。你可以轻松修改代码实现最大堆，只需将比较符号 < 改为 > 即可。

总结

本文详细讲解了 C++堆数据结构 的原理与实现，涵盖了最小堆最大堆的区别、核心操作以及完整代码。希望你能动手实践，加深理解。如果你正在准备面试或学习算法，掌握C++优先队列的底层实现将为你打下坚实基础。

关键词回顾：C++堆数据结构、堆的实现、C++优先队列、最小堆最大堆