堆与优先队列：二叉堆与 Top-K 问题

数据结构全景：堆的定义与分类

在计算机科学中，堆（Heap） 是一种特殊的树形数据结构，它满足堆属性：在一个最大堆中，对于任意节点，其值总是不大于父节点的值；在最小堆中，节点的值总是不小于父节点的值。堆是实现优先队列最高效的工具之一，它并非排序数组，而是维护了一种偏序关系，专注于快速获取极值。

堆的核心性质

• 结构性：通常实现为完全二叉树，逻辑结构紧凑，可以用数组无缝存储，无需指针。
• 堆序性：最大堆的根节点为全局最大值，最小堆反之。
• 操作复杂度：插入和删除极值均为 O(log n)，查看极值为 O(1)。

常见堆的变体

对于绝大多数应用场景，二叉堆凭借其简洁性和缓存友好性成为首选，本教程将围绕二叉堆展开。

二叉堆的底层实现与操作

二叉堆将完全二叉树映射到一维数组中，索引从 1 开始（也可从 0，公式稍作调整）。假设节点索引为 i：

• 父节点索引：i / 2
• 左孩子索引：2 * i
• 右孩子索引：2 * i + 1

这种存储方式避免了显式指针，使得内存连续，缓存命中率极高。

插入操作：上浮（Sift Up / Bubble Up）

新元素被放置在数组末尾（保持结构性），随后通过反复与父节点比较并交换，向上“冒泡”直到满足堆序性。

算法伪代码（最小堆）：
insert(value):
    heap.append(value)
    i = heap.size - 1
    while i > 0 and heap[i] < heap[parent(i)]:
        swap(heap[i], heap[parent(i)])
        i = parent(i)

删除极值：下沉（Sift Down / Bubble Down）

删除操作总是移除根节点（最小值或最大值）。将数组最后一个元素移至根位置，然后将其与两个子节点中较小（或较大）者交换，不断下沉直到堆序恢复。

extract_min():
    if heap.empty() return error
    root = heap[0]
    heap[0] = heap[heap.size - 1]
    heap.pop_back()
    sift_down(0)
    return root

sift_down(i):
    while left_child(i) < heap.size:
        smaller_child = left_child(i)
        if right_child(i) < heap.size and heap[right_child(i)] < heap[left_child(i)]:
            smaller_child = right_child(i)
        if heap[i] <= heap[smaller_child]:
            break
        swap(heap[i], heap[smaller_child])
        i = smaller_child

建堆：原地线性时间构建

对于已有数组，可采用自底向上的下沉操作，从最后一个非叶节点向前遍历，将每个子树堆化。该操作的复杂度为 O(n)，而非直觉上的 O(n log n)。

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

优先队列：堆的抽象封装

优先队列（Priority Queue） 是一种抽象数据类型，每个元素关联一个优先级，出队时总是优先级最高（或最低）的元素先被移除。堆提供了完美的底层支持，使得插入和删除都能在 O(log n) 时间内完成。

优先队列的标准接口

• enqueue(element, priority)：插入元素，时间复杂度 O(log n)
• dequeue()：移除并返回最高优先级元素，O(log n)
• peek()：查看最高优先级元素，O(1)
• change_priority(element, new_priority)：更新优先级，O(log n)（需额外索引映射）

实际编程语言中的使用

• Python：heapq 模块提供最小堆函数，列表原地操作。如需最大堆，可对值取相反数。
• Java：PriorityQueue 类默认最小堆，可传入 Comparator 定制排序。
• C++：std::priority_queue 默认最大堆，可通过 std::greater 改为最小堆。

优先队列在任务调度、事件驱动模拟、数据压缩（赫夫曼树）等场景中被广泛应用。而它最经典的面试应用，当属 Top-K 问题。

Top-K 问题：海量数据中的“最值筛选术”

Top-K 问题描述为：从海量数据中找出频率最高、值最大或最小的 K 个元素。面对内存无法容纳全部数据的场景，基于堆的解法能以优雅的空间效率和时间效率给出答案。

通用解法框架

根据寻找的是“最大 K 个”还是“最小 K 个”，选择对应的堆类型：

核心思想：维护一个容量为 K 的堆，遍历数据流，当堆未满时直接插入；当堆满时，新元素与堆顶（当前“门槛”）比较，若更有资格留在 Top-K 中，则替换堆顶并调整。这样堆中始终保存着当前已扫描数据中符合条件的 K 个元素，空间复杂度 O(K)，单次处理复杂度 O(log K)，总复杂度 O(N log K)。

实例：海量日志中查找访问频率最高的 10 个 IP

1. 使用哈希表统计每个 IP 的出现次数。
2. 构建一个容量为 10 的最小堆，比较依据为 IP 的频率。
3. 遍历哈希表：
   • 前 10 个 IP 直接入堆。
   • 之后的 IP，若频率大于堆顶（堆中最小频率），则弹出堆顶并插入新 IP。
4. 遍历结束，堆中留下的 10 个 IP 即为 Top-10。

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    counter = Counter(nums)
    min_heap = []
    for num, freq in counter.items():
        if len(min_heap) < k:
            heapq.heappush(min_heap, (freq, num))
        else:
            if freq > min_heap[0][0]:
                heapq.heapreplace(min_heap, (freq, num))
    return [num for freq, num in min_heap]

延伸对比：排序法 vs 快速选择 vs 堆

• 全排序：O(N log N)，简单但高开销，不适合大数据量。
• 快速选择：O(N) 期望时间，但需要修改数组且会对原数据全量加载，无法处理流式数据。
• 堆方法：O(N log K)，支持动态数据流，内存占用仅为 O(K)，是海量数据和实时系统的首选方案。

进阶技巧：自定义优先级与多条件排序

实际业务中，优先级可能由多个字段决定，例如任务调度需同时考虑紧急程度与等待时间。此时可自定义堆元素为复合结构体，并规定比较规则。

在 Python 中，元组按元素顺序比较，可将优先级作为第一维，额外信息作为后续维。对于无法直接比较的对象，可封装类并实现 __lt__() 方法。

示例：多关键词排序的 Top-K

class Task:
    def __init__(self, urgent, wait_time, name):
        self.urgent = urgent
        self.wait_time = wait_time
        self.name = name
    def __lt__(self, other):
        # 优先紧急，紧急相同则等待时间短者优先
        if self.urgent != other.urgent:
            return self.urgent > other.urgent  # 最大堆逻辑取反
        return self.wait_time < other.wait_time

常见误区与优化建议

• 误用堆类型：求 Top K 最小元素必须使用最大堆，保证堆顶是“门槛”。许多初学者因习惯最小堆而错误地使用，导致维护的是最小的 K 个数而非最值。
• 堆空间无限增长：在流式处理中必须严格控制堆大小，每次插入前检查长度。
• 建堆优化遗忘：若一次性获得全量数据并需要多次出队，直接 heapify O(n) 建堆远比逐个插入高效。
• 优先级变更：标准库通常不支持动态修改堆内元素优先级，可采用“惰性删除”：标记旧元素为无效，插入新元素，出队时跳过无效项。

总结：堆与优先队列的思维模型

堆为我们提供了“动态极值维护”的范式，它不追求全局有序，而是将计算资源聚焦在最重要的元素上。掌握二叉堆的实现和 Top-K 模型，不仅能应对大量面试算法题，更是设计实时数据管道、性能监控、推荐系统召回层等工业系统的基础能力。从二叉堆开始，逐步延伸至可合并堆与并发优先队列，你的数据结构武器库将更加完善。