Java集合Queue-PriorityQueue的方法

# Java集合Queue-PriorityQueue的方法

## 概述
`PriorityQueue`是Java集合框架中實現`Queue`接口的重要類，基于優先級堆（通常是最小堆）實現。與普通隊列的FIFO原則不同，`PriorityQueue`會根據元素的自然順序或自定義`Comparator`進行動態排序，保證每次出隊操作總是返回當前隊列中的最高優先級元素。

## 核心方法詳解

### 1. 構造方法
```java
// 默認初始容量(11)和自然排序
PriorityQueue<Integer> pq1 = new PriorityQueue<>();

// 指定初始容量
PriorityQueue<Integer> pq2 = new PriorityQueue<>(20);

// 使用自定義Comparator
PriorityQueue<String> pq3 = new PriorityQueue<>(
    (a,b) -> b.length() - a.length()  // 按字符串長度降序
);

// 從其他集合創建
List<Integer> list = Arrays.asList(5,3,8);
PriorityQueue<Integer> pq4 = new PriorityQueue<>(list);

2. 元素操作

添加元素

boolean add(E e)  // 插入元素，失敗時拋出異常
boolean offer(E e) // 推薦使用，插入失敗返回false

// 示例：
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(10);  // 返回true
pq.add(5);     // 隊列變為[5,10]

獲取元素

E peek()  // 獲取但不移除隊首元素（空隊列返回null）
E element() // 功能同peek()，但空隊列拋出NoSuchElementException

// 示例：
Integer val = pq.peek();  // 返回5

移除元素

E poll()  // 移除并返回隊首元素（空隊列返回null）
E remove() // 功能同poll()，但空隊列拋出異常
boolean remove(Object o) // 刪除指定元素

// 示例：
pq.poll();    // 移除并返回5
pq.remove(10); // 手動移除元素10

3. 輔助方法

int size()         // 返回元素數量
void clear()       // 清空隊列
boolean contains(Object o) // 檢查元素是否存在
Object[] toArray() // 轉為對象數組

特性與注意事項

排序特性

• 默認最小堆結構，可通過Comparator反轉：

// 創建最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
    Collections.reverseOrder()
);

時間復雜度

使用限制

1. 不允許null元素：添加null會拋出NullPointerException
2. 非線程安全：多線程環境需使用PriorityBlockingQueue
3. 迭代順序不確定：迭代器不保證按優先級順序遍歷

典型應用場景

1. 任務調度系統

PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparing(Task::getPriority)
);
taskQueue.offer(new Task("緊急修復", 1));
taskQueue.offer(new Task("日常維護", 3));
Task nextTask = taskQueue.poll();  // 總是獲取優先級最高的任務

2. Top K問題

// 找出最大的K個元素
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
    minHeap.offer(num);
    if (minHeap.size() > k) {
        minHeap.poll();
    }
}

3. 合并有序鏈表

PriorityQueue<ListNode> pq = new PriorityQueue<>(
    Comparator.comparingInt(a -> a.val)
);
// 將各鏈表頭節點入隊
while (!pq.isEmpty()) {
    ListNode min = pq.poll();
    // 處理min節點...
}

與相關類的對比

總結

PriorityQueue是處理優先級任務的理想選擇，其核心優勢在于動態維護元素順序。雖然相比普通隊列有額外的性能開銷，但在需要按優先級處理的場景下能顯著簡化代碼邏輯。使用時需注意其非線程安全特性和特殊的排序機制。 “`