堆与优先队列

1. 堆的基本概念

1.1 堆的定义

堆（Heap）是一种特殊的完全二叉树，满足以下性质：

• 最大堆：每个节点的值 ≥ 其子节点的值（根节点最大）
• 最小堆：每个节点的值 ≤ 其子节点的值（根节点最小）

最大堆:                  最小堆:
        9                       1
       / \                     / \
      8   7                   2   3
     / \ / \                 / \ / \
    5  6 4  3               6  5 4  7

1.2 堆的数组表示

由于堆是完全二叉树，可以用数组紧凑存储，无需指针：

数组索引:  0  1  2  3  4  5  6
值:       9  8  7  5  6  4  3

树形对应:
           [0]=9
          /      \
      [1]=8    [2]=7
      /    \    /   \
  [3]=5 [4]=6 [5]=4 [6]=3

索引关系（0-based）：

索引关系（1-based）：

1.3 堆的核心操作

2. 堆的核心操作实现

2.1 上浮（Sift Up / Swim）

插入新元素后，将其放在数组末尾，然后与父节点比较，不满足堆性质则交换，直到满足为止。

插入 9 到最大堆:

初始: [8, 5, 7, 3, 4, 6, 9]  ← 9 在末尾
  上浮: 9 > 7 → 交换
        [8, 5, 9, 3, 4, 6, 7]
  上浮: 9 > 8 → 交换
        [9, 5, 8, 3, 4, 6, 7]  ← 完成

// Java：最大堆的上浮操作（0-based）
private void siftUp(int[] heap, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] <= heap[parent]) break;
        swap(heap, i, parent);
        i = parent;
    }
}

# Python：最大堆的上浮操作
def sift_up(heap, i):
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] <= heap[parent]:
            break
        heap[i], heap[parent] = heap[parent], heap[i]
        i = parent

2.2 下沉（Sift Down / Sink）

删除堆顶后，将末尾元素移到堆顶，然后与较大的子节点比较，不满足堆性质则交换，直到满足为止。

删除最大堆堆顶 9:

初始: [9, 5, 8, 3, 4, 6, 7]
  末尾补位: [7, 5, 8, 3, 4, 6]  ← 7 移到堆顶
  下沉: 7 < 8 → 与 8 交换
        [8, 5, 7, 3, 4, 6]  ← 完成

// Java：最大堆的下沉操作（0-based）
private void siftDown(int[] heap, int i, int size) {
    while (true) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }
        if (largest == i) break;
        swap(heap, i, largest);
        i = largest;
    }
}

# Python：最大堆的下沉操作
def sift_down(heap, i, size):
    while True:
        left = 2 * i + 1
        right = 2 * i + 2
        largest = i

        if left < size and heap[left] > heap[largest]:
            largest = left
        if right < size and heap[right] > heap[largest]:
            largest = right
        if largest == i:
            break
        heap[i], heap[largest] = heap[largest], heap[i]
        i = largest

2.3 完整的最大堆实现

// Java：最大堆完整实现
public class MaxHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity];
        this.size = 0;
    }

    public void push(int val) {
        if (size == capacity) throw new RuntimeException("Heap is full");
        heap[size] = val;
        siftUp(size);
        size++;
    }

    public int pop() {
        if (size == 0) throw new RuntimeException("Heap is empty");
        int top = heap[0];
        heap[0] = heap[--size];
        siftDown(0);
        return top;
    }

    public int peek() {
        if (size == 0) throw new RuntimeException("Heap is empty");
        return heap[0];
    }

    public boolean isEmpty() { return size == 0; }
    public int size() { return size; }

    private void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[i] <= heap[parent]) break;
            swap(i, parent);
            i = parent;
        }
    }

    private void siftDown(int i) {
        while (true) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int largest = i;
            if (left < size && heap[left] > heap[largest]) largest = left;
            if (right < size && heap[right] > heap[largest]) largest = right;
            if (largest == i) break;
            swap(i, largest);
            i = largest;
        }
    }

    private void swap(int i, int j) {
        int tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }
}

# Python：最小堆完整实现
class MinHeap:
    def __init__(self):
        self.heap = []

    def push(self, val):
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        top = self.heap[0]
        last = self.heap.pop()
        if self.heap:
            self.heap[0] = last
            self._sift_down(0)
        return top

    def peek(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        return self.heap[0]

    def __len__(self):
        return len(self.heap)

    def _sift_up(self, i):
        while i > 0:
            parent = (i - 1) // 2
            if self.heap[i] >= self.heap[parent]:
                break
            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
            i = parent

    def _sift_down(self, i):
        n = len(self.heap)
        while True:
            left = 2 * i + 1
            right = 2 * i + 2
            smallest = i
            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 == i:
                break
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            i = smallest

3. 建堆操作

3.1 自顶向下建堆（逐个插入）

逐个插入元素，每次插入后执行上浮：

// 时间复杂度：O(n log n)
public MaxHeap(int[] arr) {
    this.heap = new int[arr.length];
    this.size = 0;
    this.capacity = arr.length;
    for (int val : arr) {
        push(val); // 每次 O(log n)
    }
}

3.2 自底向上建堆（Floyd 建堆法）

将所有元素放入数组，然后从最后一个非叶子节点开始，依次执行下沉：

// 时间复杂度：O(n)！
public MaxHeap(int[] arr) {
    this.heap = arr.clone();
    this.size = arr.length;
    this.capacity = arr.length;
    // 从最后一个非叶子节点开始下沉
    for (int i = (size / 2) - 1; i >= 0; i--) {
        siftDown(i);
    }
}

# Python：Floyd 建堆
def build_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)
    return arr

3.3 建堆 O(n) 的证明

直观理解：大部分节点在底层，下沉距离短；少数节点在高层，下沉距离长。

层（从底向上）  节点数     最大下沉距离  每层总工作量
0 (叶子)        n/2        0            0
1               n/4        1            n/4 × 1
2               n/8        2            n/8 × 2
3               n/16       3            n/16 × 3
...
h               1          h            1 × h

总工作量 = Σ(n/2^(i+1) × i), i=0 to h
         = n × Σ(i/2^(i+1))
         ≤ n × 1  （因为 Σ(i/2^(i+1)) 收敛于 1）
         = O(n)

4. 堆排序

堆排序利用最大堆的性质，每次取出堆顶（最大值）放到数组末尾：

// Java：堆排序
public static void heapSort(int[] arr) {
    int n = arr.length;

    // 1. 建最大堆 O(n)
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, i, n);
    }

    // 2. 逐个提取最大值 O(n log n)
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);     // 堆顶与末尾交换
        siftDown(arr, 0, i); // 对剩余元素下沉
    }
}

# Python：堆排序
def heap_sort(arr):
    n = len(arr)

    # 建最大堆
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)

    # 逐个提取
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        sift_down(arr, 0, i)

    return arr

堆排序特性：

5. 优先队列

5.1 优先队列概念

优先队列（Priority Queue）是一种抽象数据类型，每次出队的元素是优先级最高（或最低）的元素。堆是优先队列最常见的底层实现。

5.2 各语言优先队列

// Java：默认最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
minHeap.poll(); // 1

// 最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.offer(3);
maxHeap.poll(); // 5

// 自定义比较器
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

# Python：heapq 模块（最小堆）
import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
heapq.heappop(heap)  # 1

# 最大堆技巧：取负数
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -1)
-heapq.heappop(max_heap)  # 5

# 建堆
arr = [3, 1, 4, 1, 5, 9]
heapq.heapify(arr)  # O(n)

// C++：priority_queue（默认最大堆）
#include <queue>

std::priority_queue<int> maxHeap;
maxHeap.push(5);
maxHeap.push(1);
maxHeap.top();  // 5
maxHeap.pop();

// 最小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

6. Top-K 问题

Top-K 问题是堆/优先队列最经典的应用场景：从 n 个元素中找出最大/最小的 k 个。

6.1 方法对比

6.2 最小堆求 Top-K 大

// Java：数组中第 K 大的元素（LeetCode 215）
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // 移除最小的，保留最大的 k 个
        }
    }
    return minHeap.peek();
}

# Python：前 K 个高频元素（LeetCode 347）
import heapq
from collections import Counter

def topKFrequent(nums, k):
    count = Counter(nums)
    # 堆元素: (-频率, 数字)，用负数模拟最大堆
    return [num for _, num in heapq.nlargest(k, count.items(), key=lambda x: x[1])]

6.3 快速选择算法

# Python：快速选择求第 K 大（平均 O(n)）
import random

def findKthLargest(nums, k):
    target = len(nums) - k  # 第 k 大 = 排序后第 target 个

    def partition(left, right):
        pivot_idx = random.randint(left, right)
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        pivot = nums[right]
        i = left
        for j in range(left, right):
            if nums[j] <= pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[right] = nums[right], nums[i]
        return i

    left, right = 0, len(nums) - 1
    while left <= right:
        pos = partition(left, right)
        if pos == target:
            return nums[pos]
        elif pos < target:
            left = pos + 1
        else:
            right = pos - 1
    return -1

7. 优先队列的经典应用

7.1 合并 K 个有序链表

// Java：合并 K 个升序链表（LeetCode 23）
public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode node : lists) {
        if (node != null) pq.offer(node);
    }

    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    while (!pq.isEmpty()) {
        ListNode min = pq.poll();
        curr.next = min;
        curr = curr.next;
        if (min.next != null) {
            pq.offer(min.next);
        }
    }
    return dummy.next;
}

7.2 数据流中位数

// Java：数据流的中位数（LeetCode 295）
class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // 左半部分（较小值）
    private PriorityQueue<Integer> minHeap; // 右半部分（较大值）

    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }
        // 平衡两个堆的大小
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
        return maxHeap.peek();
    }
}

7.3 任务调度器

# Python：任务调度器（LeetCode 621）
import heapq
from collections import Counter, deque

def leastInterval(tasks, n):
    count = Counter(tasks)
    max_heap = [-c for c in count.values()]
    heapq.heapify(max_heap)

    time = 0
    queue = deque()  # (count, available_time)

    while max_heap or queue:
        time += 1
        if max_heap:
            cnt = heapq.heappop(max_heap) + 1  # 负数 +1
            if cnt != 0:
                queue.append((cnt, time + n))

        if queue and queue[0][1] == time:
            heapq.heappush(max_heap, queue.popleft()[0])

    return time

8. 堆的变体

8.1 二项堆

• 由多棵二项树组成的森林
• 支持高效合并（O(log n)）
• 是斐波那契堆的基础

8.2 斐波那契堆

• 懒惰合并策略

  操作	二叉堆	斐波那契堆（均摊）
  插入	O(log n)	O(1)
  查找最小	O(1)	O(1)
  删除最小	O(log n)	O(log n)
  合并	O(n)	O(1)
  减小键值	O(log n)	O(1)

斐波那契堆在 Dijkstra 算法中将时间复杂度从 O((V+E) log V) 优化到 O(E + V log V)，但实际常数大，工程中较少使用。

8.3 索引堆

普通堆无法在 O(log n) 内修改指定位置的元素值。索引堆通过维护一个索引数组解决这个问题：

# Python：索引最小堆
class IndexMinHeap:
    def __init__(self, n):
        self.pq = [0] * (n + 1)   # 索引堆，1-based
        self.qp = [-1] * (n + 1)  # 反向索引：qp[i] 表示 i 在 pq 中的位置
        self.keys = [None] * n     # 存储实际值
        self.size = 0

    def insert(self, i, key):
        self.size += 1
        self.qp[i] = self.size
        self.pq[self.size] = i
        self.keys[i] = key
        self._sift_up(self.size)

    def change_key(self, i, key):
        self.keys[i] = key
        self._sift_up(self.qp[i])
        self._sift_down(self.qp[i])

9. 总结

堆是优先队列的最佳实现，其 O(n) 的建堆复杂度和 O(log n) 的插入删除复杂度使其在 Top-K 问题、调度系统、图算法（Dijkstra/Prim）等场景中不可替代。理解上浮和下沉两个核心操作，是掌握堆的关键。