您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

Java PriorityQueue 優先隊列完整使用指南與自定義比較器實戰

編輯：C++ 入門

Java PriorityQueue 深度解析：從基本用法到自定義排序策略

PriorityQueue 是 Java 集合框架中基於優先堆實現的無界優先隊列。元素按自然順序或自定義 Comparator 排序，隊首始終是「最小」元素（默認最小堆）。本文通過「斑馬身高排序」完整示例，講解核心 API、比較器設計及常見陷阱。

核心特性速覽

非線程安全（多線程環境用 PriorityBlockingQueue）
不允許 null 元素
默認自然順序（實現 Comparable），可通過構造函數傳入 Comparator
入隊 offer()/add()、出隊 poll()/remove()、查看隊首 peek()/element() 均為 O(log n)

完整實戰代碼：按身高與名字排序斑馬

import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueTest {
    private static final int INITIAL_CAPACITY = 10;

    public static void main(String[] args) {
        new PriorityQueueTest().test();
    }

    private void test() {
        // 自定義比較器：先比身高升序，身高相同再比名字字典序
        PriorityQueue pq = new PriorityQueue<>(INITIAL_CAPACITY, new ZebraComparator());
        
        // 添加測試數據
        pq.add(new Zebra("a", 130));
        pq.add(new Zebra("b", 130));
        pq.add(new Zebra("c", 130));
        pq.add(new Zebra("d", 130));
        pq.add(new Zebra("a", 110)); // 身高最矮
        pq.add(new Zebra("c", 120));

        System.out.println("Queue size: " + pq.size());
        
        // 依次出隊驗證順序
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
        System.out.println("Queue size after poll: " + pq.size());
    }

    // 比較器實現：返回負數=前者優先，正數=後者優先，0=相等
    static class ZebraComparator implements Comparator {
        @Override
        public int compare(Zebra z1, Zebra z2) {
            if (z1.getHeight() != z2.getHeight()) {
                return Integer.compare(z1.getHeight(), z2.getHeight()); // 身高升序
            }
            return z1.getName().compareTo(z2.getName()); // 名字字典序
        }
    }

    // 數據模型
    static class Zebra {
        private final String name;
        private final int height;
        
        public Zebra(String name, int height) {
            this.name = name;
            this.height = height;
        }
        public String getName() { return name; }
        public int getHeight() { return height; }
        @Override public String toString() { return "Zebra[name=" + name + ", height=" + height + "]"; }
    }
}

運行結果與順序解析

Queue size: 6
Zebra[name=a, height=110]   // 身高最小，優先出隊
Zebra[name=c, height=120]   // 次小
Zebra[name=a, height=130]   // 身高相同，按名字 a < b < c < d
Zebra[name=b, height=130]
Zebra[name=c, height=130]
Zebra[name=d, height=130]
Queue size after poll: 0

關鍵技術點詳解

1. Comparator 設計原則

保證自反性：compare(a,b) == -compare(b,a)
保證傳遞性：compare(a,b)>0 && compare(b,c)>0 => compare(a,c)>0
建議與 equals() 一致：compare(a,b)==0 應暗示 a.equals(b)
優先使用 Integer.compare()、Comparator.comparing() 等 JDK 8+ 靜態工具方法，避免減法溢出

2. 常見誤區與最佳實踐

誤區	正確做法
直接用減法比較 int：`return a.height - b.height`	用 `Integer.compare(a.height, b.height)` 防溢出
以為隊列內部有序可直接遍歷	僅保證隊首最小，遍歷順序無意義；需用 `poll()` 依次取出
多線程直接用 PriorityQueue	改用 `PriorityBlockingQueue` 或外部加鎖
插入 null 元素	拋出 NPE，嚴禁插入 null

3. 擴容機制與性能提示

默認初始容量 11，擴容公式：newCapacity = oldCapacity * 1.5 + 1
可預估數據量通過構造函數指定 initialCapacity 減少擴容開銷
大量數據場景考慮批量構建：PriorityQueue pq = new PriorityQueue<>(list); O(n) 堆化優於逐個插入 O(n log n)