堆与优先队列 (Heaps and Priority Queues)

heappriority queueLeetCodealgorithminterview

堆与优先队列 (Heaps and Priority Queues)

堆是一种特殊的完全二叉树，常用来实现优先队列。堆具有以下特性：

  • 完全二叉树结构
  • 每个节点的值都大于等于（最大堆）或小于等于（最小堆）其子节点的值

基础概念

堆的结构

最大堆:               最小堆:
       100                  1
      /    \              /  \
     19    36            4    2
    /  \   /            / \   /
   17   3 25           17  5  3

数组表示

数组索引关系:
parent(i) = (i-1)/2
left_child(i) = 2i + 1
right_child(i) = 2i + 2

最大堆数组: [100, 19, 36, 17, 3, 25]
索引:        0    1   2   3   4   5

基本操作

  1. 上浮（Heapify Up）
插入50:
       100                    100
      /    \                /    \
     19    36     →        50    36
    /  \   /              /  \   /
   17   3 25             17   3 25
   /                     
  50                     

数组: [100,19,36,17,3,25,50] → [100,50,36,17,3,25,19]
  1. 下沉（Heapify Down）
删除根节点:
       100                    50
      /    \                /    \
     50    36     →        19    36
    /  \   /              /  \   /
   17   3 25             17   3 25

数组: [100,50,36,17,3,25] → [50,19,36,17,3,25]

经典问题

1. 数组中的第K个最大元素

LeetCode 215 - Kth Largest Element in an Array

使用最小堆维护K个最大元素:

输入: [3,2,1,5,6,4], k=2

堆的构建过程:
1. [3]
2. [2,3]
3. [1,2,3] → [2,3]    (保持大小为2)
4. [2,3,5] → [3,5]
5. [3,5,6] → [5,6]
6. [4,5,6] → [5,6]

返回: 5
def findKthLargest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

2. 合并K个排序链表

LeetCode 23 - Merge k Sorted Lists

使用最小堆优化多路归并:

输入链表:
1->4->5
1->3->4
2->6

最小堆过程:
初始: [1,1,2]
步骤1: 1 [1,2,4]
步骤2: 1 [2,3,4]
步骤3: 2 [3,4,4]
步骤4: 3 [4,4,5]
...

输出: 1->1->2->3->4->4->5->6
def mergeKLists(lists):
    heap = []
    # 将所有链表的头节点入堆
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))
    
    dummy = ListNode(0)
    curr = dummy
    
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    
    return dummy.next

3. 滑动窗口最大值

LeetCode 239 - Sliding Window Maximum

使用最大堆维护窗口元素:

输入: nums = [1,3,-1,-3,5,3,6,7], k = 3

窗口滑动过程:
[1,3,-1]   → 3
[3,-1,-3]  → 3
[-1,-3,5]  → 5
[-3,5,3]   → 5
[5,3,6]    → 6
[3,6,7]    → 7

输出: [3,3,5,5,6,7]
def maxSlidingWindow(nums, k):
    result = []
    heap = []  # (value, index)
    
    for i, num in enumerate(nums):
        # 添加当前元素
        heapq.heappush(heap, (-num, i))
        
        # 如果窗口已形成
        if i >= k - 1:
            # 移除窗口外的元素
            while heap and heap[0][1] <= i - k:
                heapq.heappop(heap)
            result.append(-heap[0][0])
    
    return result

4. 最小会议室数量

LeetCode 253 - Meeting Rooms II

使用最小堆跟踪会议结束时间:

输入: [[0,30],[5,10],[15,20]]

时间线处理:
0  : 开始会议1 [30]
5  : 开始会议2 [10,30]
10 : 结束会议2 [30]
15 : 开始会议3 [20,30]
20 : 结束会议3 [30]
30 : 结束会议1 []

返回: 2（最多同时需要2个会议室）
def minMeetingRooms(intervals):
    if not intervals:
        return 0
        
    # 按开始时间排序
    intervals.sort(key=lambda x: x[0])
    
    # 最小堆存储结束时间
    rooms = []
    heapq.heappush(rooms, intervals[0][1])
    
    for i in range(1, len(intervals)):
        # 如果当前会议开始时间大于最早结束时间
        if intervals[i][0] >= rooms[0]:
            heapq.heappop(rooms)
        heapq.heappush(rooms, intervals[i][1])
    
    return len(rooms)

高级应用

1. 对顶堆

中位数维护:
最大堆(左半部分)    最小堆(右半部分)
   [1,2,3]            [4,5,6]
      3      →          4
    /   \             /   \
   1     2           5     6

2. 多路归并

K路归并示意:
  [1,4,7]
  [2,5,8]  →  MinHeap  →  [1,2,3,4,5,6,7,8,9]
  [3,6,9]

3. 定时器实现

任务调度堆:
       (2s)
      /     \
   (5s)     (3s)
   /   \
(7s)  (6s)

常见技巧

  1. 使用堆优化排序
  2. 维护固定大小的堆
  3. 延迟删除
  4. 多路归并优化
  5. 对顶堆应用

相关题目