堆与优先队列实战

简介

堆（Heap）是一种基于完全二叉树结构实现的高效数据结构，它满足特定的堆序性质。在算法竞赛与工程实践中，堆通常以优先队列（Priority Queue）的形式被使用，成为解决一系列复杂问题的核心工具。与普通队列“先进先出”的规则不同，优先队列遵循“优先级最高者先出”的原则，这使得它能够动态地处理不断变化的数据集，并快速获取当前的最值。

本章将深入探讨堆的内部原理、关键操作及其在经典算法问题中的应用。我们将从堆的基本性质与操作入手，逐步深入到其在Top K问题、数据流中位数、多路归并等场景下的实战应用。最后，我们将剖析如何利用堆这一数据结构对经典的Dijkstra最短路径算法进行关键优化，显著提升其性能。掌握堆与优先队列，是迈向算法精通之路的必备阶梯。

核心概念

堆的结构与性质

堆在逻辑上是一棵完全二叉树，这意味着除了最后一层，其他层都是满的，并且最后一层的节点尽可能靠左排列。这种结构特性使得堆可以使用一个简单的数组来高效存储，而无需使用指针。对于数组中下标为 i（从0开始计数）的节点，其父节点的下标为 (i-1)//2，左子节点的下标为 2*i+1，右子节点的下标为 2*i+2。

堆的核心在于其堆序性质： - 大顶堆（Max Heap）：对于任意节点，其值都大于或等于其子节点的值。因此，堆顶（根节点）存储的是整个堆中的最大值。 - 小顶堆（Min Heap）：对于任意节点，其值都小于或等于其子节点的值。因此，堆顶存储的是整个堆中的最小值。

优先队列是堆的抽象接口，它通常提供以下核心操作：push（插入元素）、pop（弹出堆顶元素，即最值）、peek（查看堆顶元素而不移除）。

堆的关键操作

所有堆操作的核心目标是维护堆序性质。主要操作通过两个基础过程“上浮”和“下沉”来实现。

1. 上浮（Swim/Shift Up）：当一个节点的值变得比其父节点更优（在大顶堆中为更大，在小顶堆中为更小）时，需要将其向上移动以恢复堆序。过程是不断将该节点与其父节点比较并交换，直至到达根节点或满足堆序。
2. 下沉（Sink/Shift Down）：当一个节点的值变得比其子节点更差时，需要将其向下移动。过程是不断将该节点与其最优的子节点（大顶堆中取最大的子节点，小顶堆中取最小的子节点）比较并交换，直至到达叶子节点或满足堆序。
3. 建堆（Heapify）：将一个无序数组转化为堆。高效的方法是从最后一个非叶子节点开始，向前遍历，对每个节点执行“下沉”操作。最后一个非叶子节点的下标为 n//2 - 1（n为数组长度）。这种方法的时间复杂度为 O(n)，优于逐个插入的 O(n log n)。
4. 插入（Push）：将新元素添加到数组末尾（即完全二叉树的最后一个位置），然后对该元素执行上浮操作。时间复杂度 O(log n)。
5. 弹出（Pop）：移除堆顶元素。通常将数组末尾元素移至堆顶，然后对新的堆顶元素执行下沉操作。时间复杂度 O(log n)。

实战示例

示例1：手动实现一个小顶堆

以下代码展示了如何用Python列表手动实现一个小顶堆，包含建堆、插入和弹出操作。

class MinHeap:
"""手动实现的小顶堆"""
def __init__(self, nums=None):
"""初始化堆。如果提供了nums，则进行建堆操作。"""
self.heap = []
if nums:
self.heap = nums[:]
self._heapify()
def _sink_down(self, idx):
"""下沉操作：维护以idx为根的子树满足小顶堆性质。"""
n = len(self.heap)
while True:
left = 2 * idx + 1
right = 2 * idx + 2
smallest = 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:
self.heap[idx], self.heap[smallest] = self.heap[smallest], self.heap[idx]
idx = smallest
else:
break  # 堆序已满足，停止下沉
def _swim_up(self, idx):
"""上浮操作：将下标为idx的元素上浮到正确位置。"""
while idx > 0:
parent = (idx - 1) // 2
# 如果当前节点比父节点小，则交换（小顶堆）
if self.heap[idx] < self.heap[parent]:
self.heap[idx], self.heap[parent] = self.heap[parent], self.heap[idx]
idx = parent
else:
break  # 堆序已满足，停止上浮
def _heapify(self):
"""建堆：将无序数组转化为堆。"""
n = len(self.heap)
# 从最后一个非叶子节点开始，向前遍历并下沉
for i in range(n // 2 - 1, -1, -1):
self._sink_down(i)
def push(self, val):
"""插入元素：添加到末尾并上浮。"""
self.heap.append(val)
self._swim_up(len(self.heap) - 1)
def pop(self):
"""弹出堆顶元素：将末尾元素移至堆顶并下沉。"""
if not self.heap:
return None
if len(self.heap) == 1:
return self.heap.pop()
top_val = self.heap[0]  # 保存堆顶值用于返回
self.heap[0] = self.heap.pop()  # 末尾元素移到堆顶
self._sink_down(0)  # 对新的堆顶执行下沉
return top_val
def peek(self):
"""查看堆顶元素而不移除。"""
return self.heap[0] if self.heap else None
# 测试手动实现的小顶堆
if __name__ == "__main__":
data = [3, 1, 6, 5, 2, 4]
print("原始数组:", data)
min_heap = MinHeap(data)
print("建堆后数组:", min_heap.heap)  # 输出应为满足小顶堆性质的数组排列
min_heap.push(0)
print("插入0后堆顶:", min_heap.peek())  # 应为 0
print("开始弹出:")
while min_heap.peek() is not None:
print(min_heap.pop(), end=' ')  # 应输出有序序列: 0 1 2 3 4 5 6

示例2：使用堆解决Top K问题

寻找数组中最大或最小的K个元素是堆的典型应用。思路是： - 找最小的K个元素：使用大顶堆。维护一个大小为K的大顶堆，当堆满后，新元素若比堆顶小，则替换堆顶并下沉。最终堆中留下的就是最小的K个元素。 - 找最大的K个元素：使用小顶堆。维护一个大小为K的小顶堆，当堆满后，新元素若比堆顶大，则替换堆顶并下沉。最终堆中留下的就是最大的K个元素。

以下使用Python内置的heapq模块（默认实现小顶堆）来寻找最大的K个元素。

import heapq
def top_k_largest(nums, k):
"""
使用小顶堆找到数组中最大的k个元素。
:param nums: 输入数组
:param k: 需要返回的元素个数
:return: 最大的k个元素列表
"""
if k <= 0 or not nums:
return []
min_heap = []  # heapq默认是小顶堆
for num in nums:
if len(min_heap) < k:
heapq.heappush(min_heap, num)  # 堆未满，直接插入
elif num > min_heap[0]:  # 堆已满，且新元素比堆顶（当前第k大）大
heapq.heapreplace(min_heap, num)  # 弹出堆顶（较小的），插入新元素
# 堆中保存的就是最大的k个元素，但不一定有序
return min_heap
# 实战测试
if __name__ == "__main__":
nums = [3, 2, 1, 5, 6, 4]
k = 2
result = top_k_largest(nums, k)
print(f"数组 {nums} 中最大的 {k} 个元素是: {result}")
# 输出可能是 [5, 6] 或 [6, 5]，因为堆内不保证顺序
# 如果需要排序，可以再对结果排序：print(sorted(result, reverse=True))

对比分析

在解决不同类型的问题时，选择正确的堆类型和策略至关重要。

最佳实践

1. 优先使用标准库：在工程和竞赛中，优先使用语言内置的优先队列实现（如Python的heapq，Java的PriorityQueue）。它们高效且稳定，能避免手动实现的潜在错误。
2. 理解堆的底层是数组：当需要将复杂对象存入堆时（如用于Dijkstra算法的(距离, 节点)元组），记住堆排序依据的是元素的比较结果。在Python中，元组按字典序比较，这非常方便。
3. 掌握“双堆”模式：对于数据流中位数这类问题，牢记“大顶堆存较小一半，小顶堆存较大一半，并保持两堆大小平衡”的模式。这是该类问题的经典模板。
4. 堆优化Dijkstra算法的关键：使用优先队列（小顶堆）替代普通队列，每次弹出当前距离起点最近的节点。这能将算法时间复杂度从O(V²)优化到O((V+E) log V)。注意，当节点距离更新后，旧值可能仍留在堆中，因此弹出时需要检查距离是否最新（“懒惰删除”法）。
5. 注意K的大小：在解决Top K问题时，如果K非常小（接近1）或非常大（接近N），可能有比堆更优的算法（如快速选择算法）。堆在K约为N/2时优势最明显。

小结

堆与优先队列是算法工具箱中不可或缺的利器，它将动态数据集最值查询的效率提升到了对数级别。理解大顶堆与小顶堆的性质，掌握上浮、下沉、建堆等核心操作，是灵活运用的基础。在实战中，堆完美契合了Top K问题、数据流中位数、多路归并等场景的需求，并能对Dijkstra等经典算法进行关键优化。牢记“最小K个用大堆，最大K个用小堆”、“中位数用双堆”等口诀，并优先借助标准库的力量，将使我们能更专注于问题逻辑本身的求解。

下一节：二叉树与递归思维