在许多应用中，我们需要快速执行一些操作，比如查询和提取数据中的最大值或最小值。举个例子，当我们需要排序学生的考试成绩时，我们可能要频繁地查找和提取最高或最低分。除此之外，这种需求还广泛存在于优先级调度、数据流处理中。
假定我们要解决这样一个问题：有一个集合，每次操作都可能从中添加数据，或取出最大值，应该怎么做？假如使用暴力，仅使用一个数组来维护，我们就需要经常对数据集进行一次遍历（值是 (O(n))）。尽管简单，但如果你需要重复地进行多次这类查询，效率就很低了。这时，二叉堆作为一种高效的数据结构，提供了更好的性能。它能够在 (O(log n)) 的时间复杂度内进行最大值或最小值的查询和删除操作，解决了暴力方法中遍历整个数组的问题。
什么是二叉堆？
二叉堆是一种特殊的二叉树（Binary Tree），对于数来说分为大堆和小堆：
- 大堆 (Max Heap): 根节点的值大于其所有子节点的值，且每个子树的根节点也满足这一性质。
- 小堆 (Min Heap): 根节点的值小于其所有子节点的值，且每个子树的根节点也满足这一性质。
这种数据结构特别适合频繁进行最大值或最小值查询的场景，他们的用途相反，但实现原理是完全一样的，对于上例的题目来说，当然就要使用大根堆。而下图是一个典型的大根堆：
50 / 30 40 / / 10 20 35 25 为什么用数组构建二叉堆？
二叉堆通常用一个数组（Array）来实现，而不是链表。这是因为：
- 数组实现可以省去链表中用于存储指针的额外空间。
- 数组实现访问子节点或父节点更加高效，通过索引计算即可完成。这样一个密集完全的二叉树更适合数组法存储。
假如设置根节点是 (0) 号，节点在第 (i) 位置，那么其左子节点在第 (2i+1) 位置，右子节点在 (2i+2) 位置，父节点在 (lfloor(i-1)/2rfloor)。假如设置根节点是 (1) 号，节点在第 (i) 位置，那么其左子节点在第 (2i) 位置，右子节点在 (2i+1) 位置，父节点在 (lfloor i/2rfloor)。
建堆时，惯例是直接在原数组上操作，将原数组视为二叉堆，并调整让其符合堆的性质。每次heapify将自身往下都进行比较和调整，保证这一条路径上有序。将每个数据从后往前都进行heapify，就可以使整个数组成为堆。当然，你也可以选择从下向上调整，这是一样的。
#include <vector> #include <iostream> using namespace std; void heapify(vector<int>& heap, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && heap[left] > heap[largest]) { largest = left; } if (right < n && heap[right] > heap[largest]) { largest = right; } if (largest != i) { swap(heap[i], heap[largest]); heapify(heap, n, largest); } } void buildHeap(vector<int>& heap) { int n = heap.size(); for (int i = n / 2 - 1; i >= 0; --i) { heapify(heap, n, i); } } 处理时间复杂度: (O(n))。构建过程需要对每个非叶子节点进行调整，每次调整的最大操作次数取决于堆的高度。这看似是一个 nlog n 的过程。但实际上，通过 heapify 从最后一个非叶节点开始逐层向上调整，总体时间复杂度为 (O(n))。虽然每次 heapify 操作的时间复杂度是 (O(log n))，但由于树的高度逐层递减，每层的节点数呈指数下降。因此，整体复杂度是 (O(n))，而不是 (O(n log n))。
堆操作：插入(push)和删除(pop)
1. 建堆 (Build Heap)
通过从底部到顶部逐层对二叉树进行调整，我们可以快速地将无序数组变为二叉堆。上述代码展示了具体的实现方法。
2. 插入操作：Push
插入新元素时，我们需要将该元素添加到数组尾部，然后通过从他开始，不断向上调整来维护堆的性质：
void push(vector<int>& heap, int value) { heap.push_back(value); int i = heap.size() - 1; while (i != 0 && heap[(i - 1) / 2] < heap[i]) { swap(heap[i], heap[(i - 1) / 2]); i = (i - 1) / 2; } } - 处理时间复杂度: (O(log n))，因为堆的高度为 (log n)，最多需要向上调整 (log n) 次。
3. 删除操作：Pop
删除堆的根节点时，惯例上，我们保存根节点为需要返回的值后，需要将堆尾元素移动到根节点，移除最后的节点（若不使用 vector 则需要额外的 n 保存数组当前使用的长度），然后通过一次向下调整来恢复堆的性质：
int pop(vector<int>& heap) { if (heap.empty()) return -1; // Error case int root = heap[0]; heap[0] = heap.back(); heap.pop_back(); heapify(heap, heap.size(), 0); return root; } 当然，你也可以从被删节点开始向上调整，最后删除最后节点。
- 处理时间复杂度: (O(log n))。调整操作涉及沿树向下的路径。
由于添加和删除总是在数组尾部进行，树总会保持一颗高密度的完全二叉树形态，以保证树高为 (log n) 左右。
拓展知识
1. 堆能解决的经典问题
堆在算法设计中有广泛的应用，其功能涵盖了许多经典问题：
- 反悔贪心问题: 在某些贪心算法中，可以通过堆动态调整选择的结果。
- Dijkstra 算法: 优化单源最短路径算法中维护优先级队列的操作。
- Huffman 编码: 使用最小堆构建最优前缀编码树。
- 动态中位数问题: 利用两个堆分别维护较小和较大部分的元素。
- 多路归并 (k) 个有序链表: 利用最小堆在每次操作中快速找到最小的头元素。
2. 堆的其他变种
二叉堆只是堆的一种，其效率适中，实现简单，但是不支持合并操作。堆的基本思想被拓展成了许多其他高级变种，每种变种适用于特定的场景：
- 斜堆（Skew Heap）: 实现简单且支持高效合并。
- 左倾堆（Leftist Heap）: 通过维护偏斜度加速合并操作。
- 二项堆（Binomial Heap）: 由一系列二项树组成，适合合并大规模数据。
- 斐波那契堆（Fibonacci Heap）: 用于优化 Dijkstra 等算法中的松弛操作。
- 配对堆（Pairing Heap）: 通过简化操作提升实际效率。
- 优先级搜索队列（Priority Search Queue）: 扩展了堆对键值对的支持。
3. 堆与优先队列的关系
优先队列是指可以进行入队和根据优先级出队的队列，而堆是实现典型优先队列的核心数据结构之一。优先队列的关键操作（插入、取最大/最小值）都可以通过堆实现高效的时间复杂度，许多语言内置了堆操作：
- C++: 使用
std::priority_queue，默认是大根堆，小根堆需自定义比较器。#include <queue> std::priority_queue<int> maxHeap; // 大根堆 std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // 小根堆 - Python: 使用
heapq模块，默认是小根堆。import heapq heap = [] heapq.heappush(heap, value) # 插入 smallest = heapq.heappop(heap) # 弹出最小值 - Java: 使用
PriorityQueue，默认是小根堆。PriorityQueue<Integer> minHeap = new PriorityQueue<>(); PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); - Go: 使用
container/heap包。import "container/heap"
通过掌握这些实现方式，可以在不同的语言中快速构建适合特定场景的优先队列，实现高效的数据处理。
