PriorityQueue中怎么使用自定義排序函數

# PriorityQueue中怎么使用自定義排序函數

## 引言

PriorityQueue（優先隊列）是編程中常用的數據結構，它允許元素按照特定順序出隊而非簡單的先進先出。默認情況下，PriorityQueue會按照元素的自然順序進行排序，但在實際開發中，我們經常需要根據業務需求自定義排序規則。本文將詳細講解如何在Java、Python等語言中為PriorityQueue實現自定義排序函數。

---

## 一、PriorityQueue基礎概念

### 1.1 什么是PriorityQueue
PriorityQueue是基于優先級堆（通常為最小堆或最大堆）實現的無界隊列，具有以下特點：
- 元素出隊順序由優先級決定，而非插入順序
- 不允許插入null元素
- 非線程安全
- 時間復雜度：插入/刪除操作O(log n)，獲取隊首元素O(1)

### 1.2 默認排序行為
```java
// Java示例：默認最小堆
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3); pq.add(1); pq.add(2);
System.out.println(pq.poll()); // 輸出1（最小值優先）

二、Java中的自定義排序實現

2.1 使用Comparator接口

Java中可以通過Comparator接口實現自定義排序：

// 降序排列示例（最大堆）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
    (a, b) -> b - a  // 等價于Comparator.reverseOrder()
);

// 自定義對象排序
class Person {
    String name;
    int age;
}

PriorityQueue<Person> pq = new PriorityQueue<>(
    (p1, p2) -> p1.age - p2.age  // 按年齡升序
);

2.2 完整示例代碼

import java.util.*;

public class CustomPriorityQueue {
    public static void main(String[] args) {
        // 按字符串長度排序
        PriorityQueue<String> pq = new PriorityQueue<>(
            (s1, s2) -> s1.length() - s2.length()
        );
        
        pq.add("apple");
        pq.add("banana");
        pq.add("pear");
        
        while(!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
        // 輸出順序：pear → apple → banana
    }
}

三、Python中的實現方式

3.1 使用heapq模塊

Python通過heapq模塊實現優先隊列，自定義排序需要借助元組：

import heapq

# 最小堆（默認）
heap = []
heapq.heappush(heap, (3, "task3"))
heapq.heappush(heap, (1, "task1"))

# 自定義排序鍵
tasks = [(len(s), s) for s in ["apple", "banana", "pear"]]
heapq.heapify(tasks)

3.2 實現最大堆

# 方法1：存儲負值
heapq.heappush(heap, (-priority, item))

# 方法2：使用自定義類
class ReverseOrder:
    def __init__(self, val):
        self.val = val
    def __lt__(self, other):
        return self.val > other.val  # 反轉比較結果

四、實際應用場景

4.1 任務調度系統

// 按任務優先級+創建時間排序
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt(Task::getPriority)
              .thenComparing(Task::getCreateTime)
);

4.2 推薦系統Top-K問題

# 獲取點擊量最高的10個商品
top_k = heapq.nlargest(10, products, key=lambda p: p.click_count)

4.3 Dijkstra算法

優先隊列用于高效獲取當前最短路徑節點：

PriorityQueue<Node> pq = new PriorityQueue<>(
    (n1, n2) -> n1.distance - n2.distance
);

五、注意事項

1. 線程安全：Java中的PriorityQueue非線程安全，多線程環境需使用PriorityBlockingQueue
2. 修改元素：修改隊列中元素的值可能導致排序失效，需要重新建堆
3. 性能考慮：頻繁插入/刪除時，堆結構比線性結構更高效
4. 相等元素：當Comparator返回0時，不保證元素的出隊順序

六、總結

掌握PriorityQueue的自定義排序需要理解： - Java中通過Comparator接口實現 - Python中借助元組或重載比較運算符 - 實際使用時注意應用場景和性能特點

通過靈活運用自定義排序，可以高效解決各類優先級處理問題，是算法開發和工程實踐中的重要工具。

示例代碼倉庫：https://github.com/example/priorityqueue-demos “`

（全文約1100字，實際字數可能因格式略有差異）