我們知道隊列是遵循先進先出（First-In-First-Out）模式的，但有些時候需要在隊列中基于優先級處理對象。舉個例子，比方說我們有一個每日交易時段生成股票報告的應用程式，需要處理大量資料并且花費很多處理時間。客戶向這個應用程式發送請求時，實際上就進入了隊列。我們需要首先處理優先客戶再處理普通使用者。在這種情況下，Java的PriorityQueue(優先隊列)會很有幫助。

PriorityQueue類在Java1.5中引入并作為 Java Collections Framework 的一部分。PriorityQueue是基于優先堆的一個無界隊列，這個優先隊列中的元素可以預設自然排序或者通過提供的Comparator（比較器）在隊列執行個體化的時排序。

優先隊列不允許空值，而且不支援non-comparable（不可比較）的對象，比如使用者自定義的類。優先隊列要求使用Java Comparable和Comparator接口給對象排序，并且在排序時會按照優先級處理其中的元素。

優先隊列的頭是基于自然排序或者Comparator排序的最小元素。如果有多個對象擁有同樣的排序，那麼就可能随機地取其中任意一個。當我們擷取隊列時，傳回隊列的頭對象。

優先隊列的大小是不受限制的，但在建立時可以指定初始大小。當我們向優先隊列增加元素的時候，隊列大小會自動增加。

PriorityQueue是非線程安全的，是以Java提供了PriorityBlockingQueue（實作BlockingQueue接口）用于Java多線程環境。

我們有一個使用者類Customer，它沒有提供任何類型的排序。當我們用它建立優先隊列時，應該為其提供一個比較器對象。

Customer.java

package com.journaldev.collections;
 
public class Customer {
 
    private int id;
    private String name;
 
    public Customer(int i, String n){
        this.id=i;
        this.name=n;
    }
 
    public int getId() {
        return id;
    }
 
    public String getName() {
        return name;
    }
 
}
           

我們使用Java随機數生成随機使用者對象。對于自然排序，我們使用Integer對象，這也是一個封裝過的Java對象。

下面是最終的測試代碼，展示如何使用PriorityQueue：

PriorityQueueExample.java

package com.journaldev.collections;
 
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
 
public class PriorityQueueExample {
 
    public static void main(String[] args) {
 
        //優先隊列自然排序示例
        Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7);
        Random rand = new Random();
        for(int i=0;i<7;i++){
            integerPriorityQueue.add(new Integer(rand.nextInt(100)));
        }
        for(int i=0;i<7;i++){
            Integer in = integerPriorityQueue.poll();
            System.out.println("Processing Integer:"+in);
        }
 
        //優先隊列使用示例
        Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator);
        addDataToQueue(customerPriorityQueue);
 
        pollDataFromQueue(customerPriorityQueue);
 
    }
 
    //匿名Comparator實作
    public static Comparator<Customer> idComparator = new Comparator<Customer>(){
 
        @Override
        public int compare(Customer c1, Customer c2) {
            return (int) (c1.getId() - c2.getId());
        }
    };
 
    //用于往隊列增加資料的通用方法
    private static void addDataToQueue(Queue<Customer> customerPriorityQueue) {
        Random rand = new Random();
        for(int i=0; i<7; i++){
            int id = rand.nextInt(100);
            customerPriorityQueue.add(new Customer(id, "Pankaj "+id));
        }
    }
 
    //用于從隊列取資料的通用方法
    private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue) {
        while(true){
            Customer cust = customerPriorityQueue.poll();
            if(cust == null) break;
            System.out.println("Processing Customer with ID="+cust.getId());
        }
    }
 
}
           

• 首頁
• 所有文章
• 資訊
• Web
• 架構
• 基礎技術
• 書籍
• 教程
• Java小組
• 工具資源

Java優先隊列（PriorityQueue）示例

2013/11/19 | 分類： 基礎技術 | 1 條評論 | 标簽： Java, 優先級隊列

分享到： 27 本文由 ImportNew - ImportNew讀者 翻譯自 journaldev。歡迎加入 翻譯小組。轉載請見文末要求。

文章由@Jaskey_Lam翻譯。如果你也希望參與類似的系列文章翻譯，可以加入我們的Java開發 和 技術翻譯 小組。

我們知道隊列是遵循先進先出（First-In-First-Out）模式的，但有些時候需要在隊列中基于優先級處理對象。舉個例子，比方說我們有一個每日交易時段生成股票報告的應用程式，需要處理大量資料并且花費很多處理時間。客戶向這個應用程式發送請求時，實際上就進入了隊列。我們需要首先處理優先客戶再處理普通使用者。在這種情況下，Java的PriorityQueue(優先隊列)會很有幫助。

PriorityQueue類在Java1.5中引入并作為 Java Collections Framework 的一部分。PriorityQueue是基于優先堆的一個無界隊列，這個優先隊列中的元素可以預設自然排序或者通過提供的Comparator（比較器）在隊列執行個體化的時排序。

優先隊列不允許空值，而且不支援non-comparable（不可比較）的對象，比如使用者自定義的類。優先隊列要求使用Java Comparable和Comparator接口給對象排序，并且在排序時會按照優先級處理其中的元素。

優先隊列的頭是基于自然排序或者Comparator排序的最小元素。如果有多個對象擁有同樣的排序，那麼就可能随機地取其中任意一個。當我們擷取隊列時，傳回隊列的頭對象。

優先隊列的大小是不受限制的，但在建立時可以指定初始大小。當我們向優先隊列增加元素的時候，隊列大小會自動增加。

PriorityQueue是非線程安全的，是以Java提供了PriorityBlockingQueue（實作BlockingQueue接口）用于Java多線程環境。

我們有一個使用者類Customer，它沒有提供任何類型的排序。當我們用它建立優先隊列時，應該為其提供一個比較器對象。

Customer.java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

package com.journaldev.collections; public class Customer { private int id; private String name; public Customer( int i, String n){ this .id=i; this .name=n; } public int getId() { return id; } public String getName() { return name; } }

我們使用Java随機數生成随機使用者對象。對于自然排序，我們使用Integer對象，這也是一個封裝過的Java對象。

下面是最終的測試代碼，展示如何使用PriorityQueue：

PriorityQueueExample.java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

package com.journaldev.collections; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Random; public class PriorityQueueExample { public static void main(String[] args) { //優先隊列自然排序示例 Queue<Integer> integerPriorityQueue = new PriorityQueue<>( 7 ); Random rand = new Random(); for ( int i= ;i< 7 ;i++){ integerPriorityQueue.add( new Integer(rand.nextInt( 100 ))); } for ( int i= ;i< 7 ;i++){ Integer in = integerPriorityQueue.poll(); System.out.println( "Processing Integer:" +in); } //優先隊列使用示例 Queue<Customer> customerPriorityQueue = new PriorityQueue<>( 7 , idComparator); addDataToQueue(customerPriorityQueue); pollDataFromQueue(customerPriorityQueue); } //匿名Comparator實作 public static Comparator<Customer> idComparator = new Comparator<Customer>(){ @Override public int compare(Customer c1, Customer c2) { return ( int ) (c1.getId() - c2.getId()); } }; //用于往隊列增加資料的通用方法 private static void addDataToQueue(Queue<Customer> customerPriorityQueue) { Random rand = new Random(); for ( int i= ; i< 7 ; i++){ int id = rand.nextInt( 100 ); customerPriorityQueue.add( new Customer(id, "Pankaj " +id)); } } //用于從隊列取資料的通用方法 private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue) { while ( true ){ Customer cust = customerPriorityQueue.poll(); if (cust == null ) break ; System.out.println( "Processing Customer with ID=" +cust.getId()); } } }

注意我用實作了Comparator接口的Java匿名類，并且實作了基于id的比較器。

當我運作以上測試程式時，我得到以下輸出：

Processing Integer:9
Processing Integer:16
Processing Integer:18
Processing Integer:25
Processing Integer:33
Processing Integer:75
Processing Integer:77
Processing Customer with ID=6
Processing Customer with ID=20
Processing Customer with ID=24
Processing Customer with ID=28
Processing Customer with ID=29
Processing Customer with ID=82
Processing Customer with ID=96
           

從輸出結果可以清楚的看到，最小的元素在隊列的頭部因而最先被取出。如果不實作Comparator，在建立customerPriorityQueue時會抛出ClassCastException。

Exception in thread "main" java.lang.ClassCastException: com.journaldev.collections.Customer cannot be cast to java.lang.Comparable
    at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:633)
    at java.util.PriorityQueue.siftUp(PriorityQueue.java:629)
    at java.util.PriorityQueue.offer(PriorityQueue.java:329)
    at java.util.PriorityQueue.add(PriorityQueue.java:306)
    at com.journaldev.collections.PriorityQueueExample.addDataToQueue(PriorityQueueExample.java:45)
    at com.journaldev.collections.PriorityQueueExample.main(PriorityQueueExample.java:25)
           

以上就是優先隊列的全部内容，如果你喜歡這篇文章，請參與分享或者評論。

原文連結： journaldev 翻譯： ImportNew.com - ImportNew讀者

譯文連結： http://www.importnew.com/6932.html

[ 轉載請保留原文出處、譯者和譯文連結。]

關于作者： ImportNew讀者