优先队列 (Priority Queue)

定义 (Definition)

优先队列是一种抽象数据类型，其中每个元素都有一个优先级，支持以下操作：

插入操作（Insert）：将一个元素插入队列中
删除最大值操作（Delete Max） 或 删除最小值操作（Delete Min）：删除并返回队列中具有最高（或最低）优先级的元素

优先队列广泛应用于调度系统、图算法（如 Dijkstra 算法和 Prim 算法）等。

A priority queue is an abstract data type where each element has a priority. It supports the following operations:

Insert Operation: Inserts an element into the queue
Delete Max Operation or Delete Min Operation: Removes and returns the element with the highest (or lowest) priority in the queue

Priority queues are widely used in scheduling systems, graph algorithms (such as Dijkstra’s and Prim’s algorithms), etc.

实现 (Implementation)

优先队列常用的数据结构有：

堆（Heap）：如二叉堆、斐波那契堆等
平衡二叉搜索树（Balanced Binary Search Tree）：如红黑树、AVL 树等

Common data structures for implementing a priority queue include:

Heap: Such as binary heap, Fibonacci heap, etc.
Balanced Binary Search Tree: Such as Red-Black tree, AVL tree, etc.

二叉堆 (Binary Heap)

二叉堆是一种常见的优先队列实现，分为最大堆和最小堆。最大堆中，每个节点的值都大于或等于其子节点的值；最小堆中，每个节点的值都小于或等于其子节点的值。

A binary heap is a common implementation of a priority queue, divided into a max-heap and a min-heap. In a max-heap, each node’s value is greater than or equal to its children’s values; in a min-heap, each node’s value is less than or equal to its children’s values.

最大堆 (Max-Heap)

插入操作 (Insert Operation)

插入新元素时，将其添加到堆的末尾，然后上浮该元素以维护堆的性质。

When inserting a new element, add it to the end of the heap and then swim it up to maintain the heap property.

def insert(heap, value):
    heap.append(value)
    swim(heap, len(heap) - 1)
 
def swim(heap, k):
    while k > 0 and heap[(k - 1) // 2] < heap[k]:
        heap[(k - 1) // 2], heap[k] = heap[k], heap[(k - 1) // 2]
        k = (k - 1) // 2

删除最大值操作 (Delete Max Operation)

删除堆顶元素，将堆的最后一个元素移到堆顶，然后下沉该元素以维护堆的性质。

When deleting the maximum element, move the last element of the heap to the top, then sink it down to maintain the heap property.

def delete_max(heap):
    max_value = heap[0]
    heap[0] = heap.pop()
    sink(heap, 0)
    return max_value
 
def sink(heap, k):
    n = len(heap)
    while 2 * k + 1 < n:
        j = 2 * k + 1
        if j + 1 < n and heap[j] < heap[j + 1]:
            j += 1
        if heap[k] >= heap[j]:
            break
        heap[k], heap[j] = heap[j], heap[k]
        k = j

复杂度 (Complexity)

插入操作： $O (lo g n)$
删除最大值/最小值操作： $O (lo g n)$
查找最大值/最小值操作： $O (1)$
Insert Operation: $O (lo g n)$
Delete Max/Min Operation: $O (lo g n)$
Find Max/Min Operation: $O (1)$

常见用法 (Common Usage)

任务调度：按照优先级处理任务
图算法：如 Dijkstra 算法、Prim 算法
事件驱动仿真：按事件发生时间顺序处理事件
Task Scheduling: Process tasks based on priority
Graph Algorithms: Such as Dijkstra’s algorithm, Prim’s algorithm
Event-Driven Simulation: Process events in the order they occur

示例 (Example)

以下示例展示了如何使用最大堆实现优先队列：

The following example demonstrates how to implement a priority queue using a max-heap:

# 初始化一个空堆
heap = []
 
# 插入元素
insert(heap, 10)
insert(heap, 20)
insert(heap, 15)
insert(heap, 30)
insert(heap, 40)
 
# 删除最大值
print(delete_max(heap))  # 输出：40
print(delete_max(heap))  # 输出：30
print(delete_max(heap))  # 输出：20
 
# 剩余堆中的元素
print(heap)  # 输出：[15, 10]

注意点 (Points to Note)

二叉堆是一种数组表示的完全二叉树，利用数组索引方便地实现堆操作
上浮（swim）和下沉（sink）操作是维持堆性质的关键
对于需要频繁插入和删除操作的问题，优先使用堆实现的优先队列
A binary heap is a complete binary tree represented by an array, making heap operations conveniently implemented using array indices
The swim and sink operations are key to maintaining the heap property
For problems requiring frequent insertions and deletions, prefer using a heap-implemented priority queue

Zephyr's Notes on ISCS & CBMS, UTokyo

Explorer