堆（Heap） 是一种特殊的完全二叉树，具有以下特点：每个节点的值都与其子节点的值存在某种特定的关系，通常有两种类型的堆：最大堆和最小堆。
Life is like a journey
i，都有 A[i] >= A[2i + 1] 且 A[i] >= A[2i + 2]（子节点的值小于等于父节点的值）。i，都有 A[i] <= A[2i + 1] 且 A[i] <= A[2i + 2]（子节点的值大于等于父节点的值）。堆提供了以下几种常见的操作：
堆通常使用数组来实现。由于堆是完全二叉树，所以它的节点可以按顺序存储在数组中，且有如下关系：
i，其父节点的索引为 (i - 1) / 2。i，其左子节点的索引为 2i + 1。i，其右子节点的索引为 2i + 2。| 操作 | 时间复杂度 |
|---|---|
| 插入（Insert） | O(log n) |
| 删除堆顶元素（Delete） | O(log n) |
| 获取堆顶元素（Peek） | O(1) |
| 堆化（Heapify） | O(n) |
堆在很多算法和数据结构中都有广泛的应用，以下是一些典型的应用场景：
#include <iostream>
#include <vector>
using namespace std;
class MaxHeap {
private:
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 heapify(int i) {
int l = left(i);
int r = right(i);
int largest = i;
if (l < heap.size() && heap[l] > heap[largest]) largest = l;
if (r < heap.size() && heap[r] > heap[largest]) largest = r;
if (largest != i) {
swap(heap[i], heap[largest]);
heapify(largest);
}
}
public:
// 插入元素
void insert(int val) {
heap.push_back(val);
int i = heap.size() - 1;
// 向上调整（上浮）
while (i > 0 && heap[parent(i)] < heap[i]) {
swap(heap[i], heap[parent(i)]);
i = parent(i);
}
}
// 删除堆顶元素
void extractMax() {
if (heap.empty()) {
cout << "Heap is empty!" << endl;
return;
}
heap[0] = heap.back();
heap.pop_back();
heapify(0);
}
// 获取堆顶元素
int getMax() {
if (!heap.empty()) return heap[0];
return -1; // 空堆返回 -1
}
// 堆化数组
void buildHeap(vector<int>& arr) {
heap = arr;
for (int i = heap.size() / 2 - 1; i >= 0; --i) {
heapify(i);
}
}
// 打印堆
void printHeap() {
for (int val : heap) {
cout << val << " ";
} cout << endl; } };
int main() { MaxHeap mh; mh.insert(10); mh.insert(20); mh.insert(15); mh.insert(30); mh.insert(40);
mh.printHeap(); // 打印堆
cout << "Max element: " << mh.getMax() << endl;
mh.extractMax();
mh.printHeap(); // 删除堆顶元素后打印堆
return 0;
}
### 8. **总结**
堆是一种高效的数据结构，广泛应用于优先队列、排序、图算法等场景。通过使用堆，可以有效地管理一组元素中的最大或最小值。堆的插入、删除操作具有 O(log n) 的时间复杂度，堆顶元素可以在 O(1) 时间内访问，适合需要频繁插入和删除操作的应用场景。