欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

解析Java中PriorityQueue優(yōu)先級隊列結構的源碼及用法

 更新時間：2016年05月17日 08:57:00   作者：pastqing  
優(yōu)先級隊列是一種隊列結構,是0個或多個元素的集合,每個元素都有一個優(yōu)先權,PriorityQueue被內(nèi)置于JDK中,本文就來解析Java中PriorityQueue優(yōu)先級隊列結構的源碼及用法.

一、PriorityQueue的數(shù)據(jù)結構

JDK7中PriorityQueue（優(yōu)先級隊列）的數(shù)據(jù)結構是二叉堆。準確的說是一個最小堆。

二叉堆是一個特殊的堆， 它近似完全二叉樹。二叉堆滿足特性：父節(jié)點的鍵值總是保持固定的序關系于任何一個子節(jié)點的鍵值，且每個節(jié)點的左子樹和右子樹都是一個二叉堆。
當父節(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值時為最大堆。 當父節(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值時為最小堆。
下圖是一個最大堆

201651785008152.png (501×371)

priorityQueue隊頭就是給定順序的最小元素。

priorityQueue不允許空值且不支持non-comparable的對象。priorityQueue要求使用Comparable和Comparator接口給對象排序，并且在排序時會按照優(yōu)先級處理其中的元素。

priorityQueue的大小是無限制的（unbounded）, 但在創(chuàng)建時可以指定初始大小。當增加隊列元素時，隊列會自動擴容。

priorityQueue不是線程安全的， 類似的PriorityBlockingQueue是線程安全的。

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

PriorityQueue是基于優(yōu)先堆的一個無界隊列，這個優(yōu)先隊列中的元素可以默認自然排序或者通過提供的Comparator（比較器）在隊列實例化的時排序。
優(yōu)先隊列不允許空值，而且不支持non-comparable（不可比較）的對象，比如用戶自定義的類。優(yōu)先隊列要求使用Java Comparable和Comparator接口給對象排序，并且在排序時會按照優(yōu)先級處理其中的元素。

優(yōu)先隊列的頭是基于自然排序或者Comparator排序的最小元素。如果有多個對象擁有同樣的排序，那么就可能隨機地取其中任意一個。當我們獲取隊列時，返回隊列的頭對象。

優(yōu)先隊列的大小是不受限制的，但在創(chuàng)建時可以指定初始大小。當我們向優(yōu)先隊列增加元素的時候，隊列大小會自動增加。

PriorityQueue是非線程安全的，所以Java提供了PriorityBlockingQueue（實現(xiàn)BlockingQueue接口）用于Java多線程環(huán)境。

二、PriorityQueue源碼分析

成員：

priavte transient Object[] queue;
private int size = 0;

1.PriorityQueue構造小頂堆的過程

這里我們以priorityQueue構造器傳入一個容器為參數(shù)PriorityQueue(Collecntion<? extends E>的例子：

構造小頂堆的過程大體分兩步：

復制容器數(shù)據(jù)，檢查容器數(shù)據(jù)是否為null

private void initElementsFromCollection(Collection<? extends E> c) {
  Object[] a = c.toArray();
  // If c.toArray incorrectly doesn't return Object[], copy it.
  if (a.getClass() != Object[].class)
    a = Arrays.copyOf(a, a.length, Object[].class);
  int len = a.length;
  if (len == 1 || this.comparator != null)
    for (int i = 0; i < len; i++)
      if (a[i] == null)
        throw new NullPointerException();
  this.queue = a;
  this.size = a.length;
}

調(diào)整，使數(shù)據(jù)滿足小頂堆的結構。
首先介紹兩個調(diào)整方式siftUp和siftDown

siftDown: 在給定初始化元素的時候，要調(diào)整元素，使其滿足最小堆的結構性質(zhì)。因此不停地從上到下將元素x的鍵值與孩子比較并做交換，直到找到元素x的鍵值小于等于孩子的鍵值（即保證它比其左右結點值?。?，或者是下降到葉子節(jié)點為止。
例如如下的示意圖，調(diào)整9這個節(jié)點：

201651785106575.png (1133×283)

private void siftDownComparable(int k, E x) {
  Comparable<? super E> key = (Comparable<? super E>)x;
  int half = size >>> 1;    // size/2是第一個葉子結點的下標
  //只要沒到葉子節(jié)點
  while (k < half) {
    int child = (k << 1) + 1; // 左孩子
    Object c = queue[child];
    int right = child + 1;
    //找出左右孩子中小的那個
    if (right < size &&
      ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
      c = queue[child = right];
    if (key.compareTo((E) c) <= 0)
      break;
    queue[k] = c;
    k = child;
  }
  queue[k] = key;
}

siftUp: priorityQueue每次新增加一個元素的時候是將新元素插入對尾的。因此，應該與siftDown有同樣的調(diào)整過程，只不過是從下（葉子）往上調(diào)整。
例如如下的示意圖，填加key為3的節(jié)點：

201651785144192.png (680×255)

private void siftUpComparable(int k, E x) {
  Comparable<? super E> key = (Comparable<? super E>) x;
  while (k > 0) {
    int parent = (k - 1) >>> 1;   //獲取parent下標
    Object e = queue[parent];
    if (key.compareTo((E) e) >= 0)
      break;
    queue[k] = e;
    k = parent;
  }
  queue[k] = key;
}

總體的建立小頂堆的過程就是：

private void initFromCollection(Collection<? extends E> c) {
    initElementsFromCollection(c);
    heapify();
  }

其中heapify就是siftDown的過程。

2.PriorityQueue容量擴容過程

從實例成員可以看出，PriorityQueue維護了一個Object[], 因此它的擴容方式跟順序表ArrayList相差不多。
這里只給出grow方法的源碼

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                     (oldCapacity + 2) :
                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
      newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
  }

可以看出，當數(shù)組的Capacity不大的時候，每次擴容也不大。當數(shù)組容量大于64的時候，每次擴容double。

三、PriorityQueue的應用

eg1：
這里給出一個最簡單的應用：從動態(tài)數(shù)據(jù)中求第K個大的數(shù)。
思路就是維持一個size = k 的小頂堆。

  //data是動態(tài)數(shù)據(jù)
  //heap維持動態(tài)數(shù)據(jù)的堆
  //res用來保存第K大的值
  public boolean kthLargest(int data, int k, PriorityQueue<Integer> heap, int[] res) {
    if(heap.size() < k) {
      heap.offer(data);
      if(heap.size() == k) {
        res[0] = heap.peek();
        return true;
      }
      return false;
    }
    if(heap.peek() < data) {
      heap.poll();
      heap.offer(data);
    }
    res[0] = heap.peek();
    return true;
  }

   
eg2：
我們有一個用戶類Customer，它沒有提供任何類型的排序。當我們用它建立優(yōu)先隊列時，應該為其提供一個比較器對象。

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隨機數(shù)生成隨機用戶對象。對于自然排序，我們使用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) {
 
    //優(yōu)先隊列自然排序示例
    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);
    }
 
    //優(yōu)先隊列使用示例
    Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator);
    addDataToQueue(customerPriorityQueue);
 
    pollDataFromQueue(customerPriorityQueue);
 
  }
 
  //匿名Comparator實現(xiàn)
  public static Comparator<Customer> idComparator = new Comparator<Customer>(){
 
    @Override
    public int compare(Customer c1, Customer c2) {
      return (int) (c1.getId() - c2.getId());
    }
  };
 
  //用于往隊列增加數(shù)據(jù)的通用方法
  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));
    }
  }
 
  //用于從隊列取數(shù)據(jù)的通用方法
  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());
    }
  }
 
}

注意我用實現(xiàn)了Comparator接口的Java匿名類，并且實現(xiàn)了基于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

從輸出結果可以清楚的看到，最小的元素在隊列的頭部因而最先被取出。如果不實現(xiàn)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)

相關文章

最新評論