C++最大堆实现方法详解（从零开始掌握堆数据结构）

为什么需要自己实现最大堆？

虽然 C++ 标准库提供了 priority_queue（默认就是最大堆），但手动实现堆有助于你深入理解 C++堆数据结构 的底层原理，对算法学习和面试都非常有帮助。

最大堆的基本操作

• 插入（Insert）：向堆中添加一个新元素，并保持堆性质。
• 删除最大值（Extract-Max）：移除并返回堆顶元素，然后重新调整堆。
• 上浮（Heapify-Up）：插入后，若破坏堆性质，则向上调整。
• 下沉（Heapify-Down）：删除后，若破坏堆性质，则向下调整。

C++ 最大堆完整实现

下面是一个完整的 最大堆C++代码 实现，使用 vector 作为底层存储：

#include <iostream>#include <vector>using namespace std;class MaxHeap {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 maxIndex = i;        int left = leftChild(i);        int right = rightChild(i);        if (left < heap.size() && heap[left] > heap[maxIndex])            maxIndex = left;        if (right < heap.size() && heap[right] > heap[maxIndex])            maxIndex = right;        if (maxIndex != i) {            swap(heap[i], heap[maxIndex]);            heapifyDown(maxIndex);        }    }public:    // 插入元素    void insert(int value) {        heap.push_back(value);        heapifyUp(heap.size() - 1);    }    // 获取最大值（不删除）    int getMax() {        if (heap.empty()) {            throw runtime_error("Heap is empty!");        }        return heap[0];    }    // 删除并返回最大值    int extractMax() {        if (heap.empty()) {            throw runtime_error("Heap is empty!");        }        int maxVal = heap[0];        heap[0] = heap.back();        heap.pop_back();        if (!heap.empty()) {            heapifyDown(0);        }        return maxVal;    }    // 检查堆是否为空    bool isEmpty() {        return heap.empty();    }    // 打印堆（用于调试）    void print() {        for (int val : heap) {            cout << val << " ";        }        cout << endl;    }};// 测试示例int main() {    MaxHeap maxHeap;    maxHeap.insert(10);    maxHeap.insert(20);    maxHeap.insert(15);    maxHeap.insert(30);    maxHeap.insert(40);    cout << "堆中元素: ";    maxHeap.print(); // 输出顺序不一定有序，但堆顶是最大值    cout << "最大值: " << maxHeap.getMax() << endl; // 40    cout << "提取最大值: " << maxHeap.extractMax() << endl; // 40    cout << "提取后堆: ";    maxHeap.print(); // 堆顶变为30    return 0;}  

代码解析

上述代码定义了一个 MaxHeap 类，包含以下关键方法：

• insert()：在末尾添加元素后调用 heapifyUp() 保证堆性质。
• extractMax()：取出堆顶后，将最后一个元素移到顶部，再调用 heapifyDown() 调整。
• heapifyUp() 和 heapifyDown() 是维护堆结构的核心递归函数。

与标准库 priority_queue 对比

C++ 标准库中的 priority_queue<int> 默认就是最大堆，等价于：

priority_queue<int> pq; // 最大堆pq.push(10);pq.push(20);cout << pq.top(); // 输出最大值  

但自己实现堆能让你更灵活地扩展功能（如删除任意元素、修改键值等），这也是理解 C++优先队列实现 原理的关键一步。

总结

通过本文，你已经学会了如何从零开始用 C++ 实现一个最大堆。这不仅加深了你对堆数据结构的理解，也为后续学习图算法（如 Dijkstra）、堆排序等打下坚实基础。记住，动手写代码才是掌握知识的最佳方式！

希望这篇关于 C++最大堆实现 的教程对你有帮助。如果你觉得有用，不妨收藏或分享给其他正在学习 C++ 的朋友！