堆

堆(Heap)是基于完全二叉树的抽象数据结构,满足堆序性:父节点的值总是大于等于(最大堆)或小于等于(最小堆)其子节点的值。堆通常用数组存储,凭借其结构特性,可在 O(1) 时间取极值,在 O(log n) 时间完成插入与删除,是实现优先队列与堆排序的核心。

二叉堆(最大堆 / 最小堆)

最大堆(Max-Heap):任意父节点 ≥ 子节点,堆顶为最大值。 最小堆(Min-Heap):任意父节点 ≤ 子节点,堆顶为最小值。

由于堆是完全二叉树,可用一维数组紧凑存储,下标关系为:

• 父节点 i 的左子节点为 2i + 1,右子节点为 2i + 2。
• 子节点 i 的父节点为 (i - 1) // 2。

这种映射使得不需要显式指针即可在数组中导航父子关系,缓存友好且实现简单。

插入(sift-up 上浮)

插入新元素时,先追加到数组末尾,再与父节点比较:若违反堆序性则交换并上移,直到满足条件或到达根。由于树高为 O(log n),上浮最多 log n 步,时间复杂度 O(log n)。

def sift_up(arr, i):
    while i > 0:
        parent = (i - 1) // 2
        if arr[parent] < arr[i]:        # 最大堆
            arr[parent], arr[i] = arr[i], arr[parent]
            i = parent
        else:
            break

删除与下沉(sift-down)

删除堆顶(最值)时,不能直接移动数组,否则破坏完全二叉树结构。标准做法是:将堆顶与最后一个元素交换,数组长度减 1,然后对新的堆顶执行下沉。下沉时选取较大的子节点(最大堆)与之比较,不满足堆序则交换并下移,时间同样 O(log n)。

下沉操作也是堆排序与建堆的核心。

heapify 与建堆 O(n)

将一个无序数组调整为堆的过程称为 heapify。直观做法是逐个插入 O(n log n),但更高效的方法是自底向上对每个非叶子节点执行一次下沉,时间复杂度为 O(n),而非 O(n log n)。

直觉上:叶子节点占 n/2,它们无需下沉;越靠近根的节点越少,但下沉步数大;总体求和后高阶项抵消,得到 O(n)。这一性质是堆优于"逐个插入建堆"的关键。

def heapify(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)

堆排序(Heap Sort)

堆排序分两阶段:

1. 建堆:对数组执行 heapify 建立最大堆,O(n)。
2. 排序:反复将堆顶(当前最大值)与末尾元素交换,堆大小减 1,然后对堆顶下沉,共 n-1 轮,每轮 O(log n),总计 O(n log n)。

堆排序原地、最坏 O(n log n)、不需要额外空间,但不稳定(相等元素的相对顺序可能改变),且常数因子较大,实际性能略逊于快速排序。

优先队列(Priority Queue)应用

堆是优先队列的经典实现,队列内元素按优先级出队,而非按到达顺序:

• Dijkstra 最短路径:每次取当前距离最小的节点,堆优化后从 O(V²) 降至 O((V + E) log V)。
• 任务调度:操作系统按优先级分派任务。
• Top K 问题:维护大小为 K 的最小堆,遍历 N 个元素,时间 O(N log K),远优于排序的 O(N log N)。
• 合并有序流:多路归并时,堆顶始终是当前最小元素,可在 O(log k) 内选出下一输出。
• 定时器/事件驱动:Netty、libuv 等框架用堆管理最近到期事件。

堆看似简单,却是众多高性能算法与系统的底座;掌握其上浮、下沉、heapify 三个原语,即可应对绝大多数面试与工程场景。