1. 什么是堆？#

堆是一种特殊的完全二叉树，它满足以下关键性质：

堆序性：堆中任意一个节点的值都必须满足与它所有子孙节点的值的大小关系。
- 在最大堆中，每个节点的值都大于或等于其子节点的值。因此，根节点是整棵树的最大值。
- 在最小堆中，每个节点的值都小于或等于其子节点的值。因此，根节点是整棵树的最小值。

关键点：堆只规定了父节点和子节点之间的大小关系，但没有规定左子节点和右子节点的大小关系。这意味着，对于同一个父节点的两个子节点，你无法确定哪个更大（在最大堆中）或哪个更小（在最小堆中）。这是堆与二叉搜索树的一个主要区别。

2. 堆的特点#

完全二叉树结构：堆总是一棵完全二叉树。这意味着除了最后一层，其他层都是满的，并且最后一层的节点都尽可能地向左排列。这个特性使得堆可以使用数组来高效地存储，而不需要像链表那样使用指针。
- 数组表示法：对于数组中索引为 i（通常从 0 开始）的节点：
  - 其父节点的索引为：(i - 1) / 2（向下取整）
  - 其左子节点的索引为：2 * i + 1
  - 其右子节点的索引为：2 * i + 2
高效的插入和删除：由于堆的结构特性，插入和删除元素后，需要通过“上浮”或“下沉”操作来重新维护堆的性质。这些操作的时间复杂度与树的高度成正比。
- 插入元素（Insert）：时间复杂度为 O(log n)。新元素被添加到数组末尾（即树的最后一个节点），然后通过“上浮”操作，与其父节点比较并交换，直到满足堆的性质。
- 删除堆顶元素（Extract-Max/Min）：时间复杂度为 O(log n)。将堆顶元素（最大值或最小值）与数组末尾的元素交换，然后删除末尾元素（即原堆顶）。之后，新的堆顶元素通过“下沉”操作，与其较大的（最大堆）或较小的（最小堆）子节点比较并交换，直到满足堆的性质。
快速访问极值：获取堆中的最大值（最大堆）或最小值（最小堆）的操作可以在 **O(1)** 时间内完成，因为极值永远在根节点（即数组的第一个元素）。

3. 堆的常见操作与代码示例（以最大堆为例）#

以下是使用 Python 列表实现最大堆的核心方法：

1
class MaxHeap:
2
    def __init__(self):
3
        self.heap = []
4

5
    def parent(self, i):
6
        return (i - 1) // 2
7

8
    def left_child(self, i):
9
        return 2 * i + 1
10

11
    def right_child(self, i):
12
        return 2 * i + 2
13

14
    def swap(self, i, j):
15
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
16

17
    def insert(self, key):
18
        # 1. 将新元素插入到末尾
19
        self.heap.append(key)
20
        # 2. 上浮操作，调整堆
21
        current = len(self.heap) - 1
22
        while current > 0 and self.heap[current] > self.heap[self.parent(current)]:
23
            p = self.parent(current)
24
            self.swap(current, p)
25
            current = p
26

27
    def heapify(self, i):
28
        # 下沉操作
29
        largest = i
30
        left = self.left_child(i)
31
        right = self.right_child(i)
32
        n = len(self.heap)
33

34
        # 找到当前节点、左子节点、右子节点中最大的那个
35
        if left < n and self.heap[left] > self.heap[largest]:
36
            largest = left
37
        if right < n and self.heap[right] > self.heap[largest]:
38
            largest = right
39

40
        # 如果最大值不是当前节点，则交换并继续向下调整
41
        if largest != i:
42
            self.swap(i, largest)
43
            self.heapify(largest) # 递归调整
44

45
    def extract_max(self):
46
        if not self.heap:
47
            return None
48
        if len(self.heap) == 1:
49
            return self.heap.pop()
50

51
        # 取出堆顶最大值
52
        max_value = self.heap[0]
53
        # 将最后一个元素移到堆顶
54
        self.heap[0] = self.heap.pop()
55
        # 对新的堆顶进行下沉操作，恢复堆的性质
56
        self.heapify(0)
57
        return max_value
58

59
    def get_max(self):
60
        return self.heap[0] if self.heap else None

4. 堆的应用#

堆的强大之处在于其高效处理“极值”问题的能力，以下是几个经典应用：

堆排序
- 思想：利用堆的特性进行排序。
  - 升序排序：构建一个最大堆，然后反复将堆顶元素（当前最大值）与堆末尾元素交换，并减小堆的大小，再对新的堆顶进行“下沉”操作。时间复杂度为 O(n log n)。
  - 降序排序：构建一个最小堆，过程类似。
优先级队列
- 这是堆最直接和重要的应用。优先级队列是一种数据结构，其中每个元素都有一个“优先级”，出队时总是优先级最高（值最大或最小）的元素先出队。
- 实现：使用堆可以高效地实现优先级队列。插入操作对应堆的 insert，出队操作对应堆的 extract_max或 extract_min。
- 应用场景：
  - 任务调度：操作系统中的进程调度，优先级高的任务先执行。
  - Dijkstra 算法：在图中寻找最短路径时，用优先级队列来选择下一个要处理的节点。
  - 哈夫曼编码：用于数据压缩。
求 Top K 问题
- 问题：从海量数据中找出最大（或最小）的 K 个元素。
- 解法：
  - 求最大的 K 个：维护一个大小为 K 的最小堆。遍历数据，如果当前元素比堆顶（当前 K 个元素中的最小值）大，就替换堆顶并调整堆。最后堆中剩下的就是最大的 K 个元素。时间复杂度为 O(n log K)，远优于排序的 O(n log n)。
  - 求最小的 K 个：维护一个大小为 K 的最大堆，思路相反。
求中位数、百分位数
- 可以使用两个堆（一个最大堆，一个最小堆）来动态维护数据流，从而高效地计算实时中位数。

5. 总结#

特性/方面	描述
本质	一种满足堆序性的完全二叉树
核心类型	最大堆（父 ≥ 子），最小堆（父 ≤ 子）
存储方式	通常使用数组，利用完全二叉树的性质
关键操作时间复杂度	插入：O(log n)，删除堆顶：O(log n)，获取极值：O(1)
主要应用	堆排序、优先级队列、Top K 问题、求中位数等

安卓中查看GID和UID

3. 堆的常见操作与代码示例（以最大堆为例）