优先队列小根堆怎么实现？

Question

**问题描述：** 在实现优先队列时，常用的一种数据结构是小根堆（Min-Heap），它能高效地支持插入元素和取出最小元素的操作。但在实际编码过程中，如何正确构建和维护一个小根堆的结构？常见的实现方式是使用数组模拟堆结构，那么在插入元素和删除堆顶元素时，如何通过“上浮”和“下沉”操作维持堆的性质？此外，在 Java、Python 或 C++ 等不同语言中，是否有现成的库可以直接实现小根堆？如果需要手动实现，其核心逻辑应包括哪些函数？

Answer 1

一、小根堆的基本概念与作用

小根堆（Min-Heap）是一种特殊的完全二叉树结构，其每个节点的值都小于或等于其子节点的值。这种结构非常适合用于实现优先队列，尤其是在需要频繁获取最小值的场景中，例如图算法中的Dijkstra算法。

堆通常使用数组来模拟树的结构，其中索引为i的节点，其左子节点为2*i+1，右子节点为2*i+2，父节点为(i-1)//2（在Python中）。

二、小根堆的构建与维护

堆的维护主要依赖于两个操作：上浮（sift up）和下沉（sift down）。

• 上浮操作：当插入新元素时，将其放置在数组末尾，然后不断与其父节点比较，若小于父节点则交换位置，直到满足堆性质。
• 下沉操作：当删除堆顶元素后，将最后一个元素移动到堆顶，然后不断与其子节点比较，若大于子节点则交换位置，直到满足堆性质。

三、不同语言中的小根堆实现

语言	标准库支持	示例代码
Java	PriorityQueue，默认为小根堆	PriorityQueue<Integer> heap = new PriorityQueue<>();
Python	heapq模块，默认为小根堆	import heapq; heap = []; heapq.heappush(heap, 5)
C++	priority_queue，默认为大根堆，需自定义比较器	priority_queue<int, vector<int>, greater<int>> minHeap;

四、手动实现小根堆的核心函数

如果标准库不满足需求，或者需要自定义比较逻辑，可以手动实现堆结构。核心函数包括：

1. insert(value)：插入新元素并执行上浮操作。
2. extractMin()：删除并返回堆顶元素，并执行下沉操作。
3. heapify(array)：将数组原地转换为堆结构。
4. siftUp(index)：将指定索引的元素向上调整。
5. siftDown(index)：将指定索引的元素向下调整。

五、手动实现示例（以Python为例）

class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, val):
        self.heap.append(val)
        self.sift_up(len(self.heap) - 1)

    def extract_min(self):
        if not self.heap:
            return None
        min_val = self.heap[0]
        last_val = self.heap.pop()
        if self.heap:
            self.heap[0] = last_val
            self.sift_down(0)
        return min_val

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

    def sift_down(self, index):
        n = len(self.heap)
        while index * 2 + 1 < n:
            left = index * 2 + 1
            right = left + 1
            min_child = left if (right < n and self.heap[right] < self.heap[left]) else left
            if self.heap[index] <= self.heap[min_child]:
                break
            self.heap[index], self.heap[min_child] = self.heap[min_child], self.heap[index]
            index = min_child
    

六、堆结构的性能分析

堆的关键操作时间复杂度如下：

操作	时间复杂度
插入元素	O(log n)
取出最小值	O(log n)
构建堆	O(n)

七、堆结构的应用场景与扩展

除了作为优先队列的基础结构，小根堆还广泛应用于以下场景：

• Top K问题（如取最大/最小K个元素）
• 合并多个有序链表
• 任务调度系统（优先级调度）
• 哈夫曼编码

此外，堆结构还可以扩展为更复杂的结构，如二项堆、斐波那契堆，以支持更高效的合并操作。

八、堆操作流程图

graph TD
    A[插入元素] --> B[添加到数组末尾]
    B --> C[执行上浮操作]
    C --> D{是否大于父节点?}
    D -- 是 --> E[停止]
    D -- 否 --> F[交换位置]
    F --> C

    G[删除堆顶] --> H[取出堆顶元素]
    H --> I[将最后一个元素移到堆顶]
    I --> J[执行下沉操作]
    J --> K{是否有更小的子节点?}
    K -- 否 --> L[停止]
    K -- 是 --> M[交换位置]
    M --> J