一、小顶堆的定义

小顶堆是堆的一种具体类型，属于完全二叉树结构，且满足其核心数值性质：每个父节点的值都小于或等于其左右子节点的值，堆顶（根节点）为整个堆的最小值。

小顶堆常用于快速获取和维护数据集的最小值，是优先队列（最小值优先）、Top-K大问题、多路归并等场景的核心底层结构。

资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

二、小顶堆的核心性质

1. 结构性质

• 小顶堆是一棵完全二叉树，除最后一层外，其余层节点数均为最大值，最后一层节点需靠左排列。
• 通常采用数组存储，若数组索引从0开始，对于索引为i的节点：
  • 左子节点索引为2i + 1
  • 右子节点索引为2i + 2
  • 父节点索引为(i - 1) // 2

2. 数值性质

• 任意父节点的值 ≤ 其左右子节点的值，堆顶（数组索引0位置）始终是堆中最小值。
• 叶子节点无后代，无需再满足额外数值约束。

三、小顶堆的核心操作

小顶堆的所有操作均为维持其数值性质，核心是上浮和下沉两个调整动作，具体操作如下：

1. 上浮（Up-Heapify）

当插入新元素时，新元素初始置于数组末尾，若其值小于父节点，需通过上浮调整位置。

• 操作逻辑：比较当前节点与父节点的值，若当前节点更小，则交换两者；重复此过程，直到当前节点值 ≥ 父节点或到达堆顶。

2. 下沉（Down-Heapify）

当堆顶元素被删除或堆内元素值被修改时，需通过下沉恢复堆的性质。

• 操作逻辑：比较当前节点与左右子节点的值，选择值最小的子节点；若当前节点值大于该子节点，则交换两者；重复此过程，直到当前节点值 ≤ 所有子节点或成为叶子节点。

3. 插入元素

1. 将新元素添加到数组末尾；
2. 对新元素执行上浮操作，恢复小顶堆性质。

4. 删除堆顶元素

1. 将堆顶元素与数组末尾元素交换；
2. 删除数组末尾的原堆顶元素；
3. 对新的堆顶元素执行下沉操作，恢复小顶堆性质。

5. 构建小顶堆

将无序数组转为小顶堆，从最后一个非叶子节点（索引为(n//2)-1，n为数组长度）开始，从下到上依次执行下沉操作。

四、小顶堆的时间复杂度

• 插入操作：时间复杂度为O(log n)，上浮操作最多遍历堆的高度（log n层）。
• 删除堆顶操作：时间复杂度为O(log n)，下沉操作的遍历次数不超过堆的高度。
• 构建堆：时间复杂度为O(n)，优于逐个插入的O(n log n)。
• 获取堆顶最小值：时间复杂度为O(1)，可直接访问数组索引0位置的元素。

五、小顶堆的实现示例

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, idx):
        """获取父节点索引"""
        return (idx - 1) // 2

    def left_child(self, idx):
        """获取左子节点索引"""
        return 2 * idx + 1

    def right_child(self, idx):
        """获取右子节点索引"""
        return 2 * idx + 2

    def swap(self, i, j):
        """交换堆中两个位置的元素"""
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def up_heapify(self, idx):
        """上浮操作，维护小顶堆性质"""
        while idx > 0 and self.heap[idx] < self.heap[self.parent(idx)]:
            self.swap(idx, self.parent(idx))
            idx = self.parent(idx)

    def down_heapify(self, idx):
        """下沉操作，维护小顶堆性质"""
        n = len(self.heap)
        while True:
            smallest = idx  # 初始假设当前节点最小
            left = self.left_child(idx)
            right = self.right_child(idx)

            # 比较左子节点
            if left < n and self.heap[left] < self.heap[smallest]:
                smallest = left
            # 比较右子节点
            if right < n and self.heap[right] < self.heap[smallest]:
                smallest = right

            # 若当前节点已是最小，停止下沉
            if smallest == idx:
                break
            self.swap(idx, smallest)
            idx = smallest

    def insert(self, val):
        """插入元素"""
        self.heap.append(val)
        self.up_heapify(len(self.heap) - 1)

    def extract_min(self):
        """删除并返回堆顶最小值"""
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        min_val = self.heap[0]
        # 堆顶与末尾元素交换，删除原堆顶
        self.heap[0] = self.heap.pop()
        # 新堆顶下沉
        self.down_heapify(0)
        return min_val

    def get_min(self):
        """获取堆顶最小值（不删除）"""
        return self.heap[0] if self.heap else None

    def build_heap(self, arr):
        """将无序数组构建为小顶堆"""
        self.heap = arr.copy()
        n = len(self.heap)
        # 从最后一个非叶子节点开始下沉
        for i in range((n // 2) - 1, -1, -1):
            self.down_heapify(i)

使用示例

# 初始化小顶堆
min_heap = MinHeap()

# 插入元素
min_heap.insert(5)
min_heap.insert(3)
min_heap.insert(8)
min_heap.insert(1)
print("堆顶最小值:", min_heap.get_min())  # 输出 1

# 提取堆顶
print("提取的最小值:", min_heap.extract_min())  # 输出 1
print("当前堆顶:", min_heap.get_min())  # 输出 3

# 用无序数组构建小顶堆
arr = [9, 4, 7, 1, 3, 6]
min_heap.build_heap(arr)
print("构建后的堆顶:", min_heap.get_min())  # 输出 1

六、小顶堆的典型应用

1. 优先队列（最小值优先）：适用于任务调度中优先处理优先级低（数值小）的任务，或事件驱动系统中优先触发时间更早的事件。
2. Top-K 大问题：维护一个大小为K的小顶堆，遍历数据时，若新元素大于堆顶则替换堆顶并下沉，最终堆中元素即为前K大值。
3. 堆排序：先构建小顶堆，再逐次提取堆顶最小值并放到数组末尾，最终得到降序数组。
4. 数据流最小值维护：实时数据流场景下，可通过小顶堆快速获取当前所有数据的最小值。
5. 多路归并排序：合并多个有序数组时，用小顶堆快速获取各数组当前最小值，实现高效归并。