数据结构与算法 / 系统课时

优先队列

优先队列

优先队列并不按进入顺序取出元素,而是始终先处理优先级最高的元素。本课使用最大堆实现插入、查看最高优先级和删除最高优先级三种操作,并验证每次调整后堆序性质仍然成立。

学习目标

  • 理解优先队列与普通队列的区别,以及最大堆为何适合作为底层结构。
  • 掌握 offer、peek 和 poll 的实现过程。
  • 能够分析三种操作的时间复杂度与空队列边界。

核心原理

最大堆是一棵完全二叉树,任意父节点都不小于它的孩子。用数组保存时,下标 i 的父节点为 (i - 1) / 2,左孩子为 2 * i + 1,右孩子为 2 * i + 2。

插入元素时,先把新值放到数组末尾,再不断与父节点比较并向上交换,这个过程称为上浮。删除最高优先级元素时,先保存根节点,再把末尾元素移到根位置,删除末尾槽位,最后让新根与较大的孩子交换并向下移动,这个过程称为下沉。

优先队列的最大堆结构与三种操作

优先队列的三个核心操作具有不同职责:

操作 作用 最大堆中的位置 时间复杂度
offer(value) 插入新元素 末尾写入后上浮 O(log⁡n)O(\log n)
peek() 查看最高优先级元素 读取根节点 O(1)O(1)
poll() 删除并返回最高优先级元素 根节点替换后下沉 O(log⁡n)O(\log n)

完整可运行示例

下面的 Java 17 程序实现一个整数最大优先队列。ArrayList 只负责动态存储,优先级顺序完全由上浮和下沉逻辑维护。

java
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class MaxPriorityQueueDemo {

    static class MaxPriorityQueue {
        private final List<Integer> heap = new ArrayList<>();

        public void offer(int value) {
            heap.add(value);
            siftUp(heap.size() - 1);
        }

        public int peek() {
            ensureNotEmpty();
            return heap.get(0);
        }

        public int poll() {
            ensureNotEmpty();

            int result = heap.get(0);
            int lastValue = heap.remove(heap.size() - 1);

            if (!heap.isEmpty()) {
                heap.set(0, lastValue);
                siftDown(0);
            }
            return result;
        }

        public boolean isEmpty() {
            return heap.isEmpty();
        }

        private void siftUp(int index) {
            while (index > 0) {
                int parent = (index - 1) / 2;
                if (heap.get(parent) >= heap.get(index)) {
                    break;
                }

                swap(parent, index);
                index = parent;
            }
        }

        private void siftDown(int index) {
            int size = heap.size();

            while (true) {
                int left = index * 2 + 1;
                int right = index * 2 + 2;
                int largest = index;

                if (left < size && heap.get(left) > heap.get(largest)) {
                    largest = left;
                }
                if (right < size && heap.get(right) > heap.get(largest)) {
                    largest = right;
                }
                if (largest == index) {
                    break;
                }

                swap(index, largest);
                index = largest;
            }
        }

        private void swap(int first, int second) {
            int temporary = heap.get(first);
            heap.set(first, heap.get(second));
            heap.set(second, temporary);
        }

        private void ensureNotEmpty() {
            if (heap.isEmpty()) {
                throw new NoSuchElementException("优先队列为空");
            }
        }

        @Override
        public String toString() {
            return heap.toString();
        }
    }

    public static void main(String[] args) {
        MaxPriorityQueue queue = new MaxPriorityQueue();

        for (int value : new int[] {4, 10, 7, 3}) {
            queue.offer(value);
        }

        System.out.println("堆数组: " + queue);
        System.out.println("最高优先级: " + queue.peek());
        System.out.println("删除最高优先级: " + queue.poll());
        System.out.println("删除后的堆: " + queue);

        while (!queue.isEmpty()) {
            System.out.println("继续删除: " + queue.poll());
        }
    }
}

将代码保存为 MaxPriorityQueueDemo.java,然后运行:

bash
javac MaxPriorityQueueDemo.java
java MaxPriorityQueueDemo

预期输出:

text
堆数组: [10, 4, 7, 3]
最高优先级: 10
删除最高优先级: 10
删除后的堆: [7, 4, 3]
继续删除: 7
继续删除: 4
继续删除: 3

复杂度与边界

堆中从叶子到根的高度为 O(log⁡n)O(\log n),所以上浮和下沉最多经过一条根到叶子的路径。底层数组占用 O(n)O(n) 空间,操作本身只使用常数个临时变量。

调用 peek() 或 poll() 前必须处理空队列。示例选择抛出 NoSuchElementException,工程中也可以返回 OptionalInt,但不要用特殊整数表示“空”,否则该整数可能与合法优先级冲突。

优先队列只保证根节点是当前最大值,不保证整个数组全局有序。若业务需要稳定处理相同优先级,可把“优先级”和“入队序号”组成复合比较键。

本课总结

  • 最大堆通过“父节点不小于孩子”保证根节点始终具有最高优先级。
  • 插入依靠上浮,删除根节点依靠末尾替换与下沉,两者复杂度均为 O(log⁡n)O(\log n)。
  • peek() 只读取根节点,因此是 O(1)O(1),但必须显式处理空队列。

下一课预告

下一课将学习“并查集基础”,掌握创建集合、查找代表元和合并集合三个操作,并理解它们如何高效维护动态连通关系。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

优先队列

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通