本篇文章為大家展示了priorityqueue怎么在JAVA中使用，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

站在用戶的角度思考問題，與客戶深入溝通，找到朔州網站設計與朔州網站推廣的解決方案，憑借多年的經驗，讓設計與互聯(lián)網技術結合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：做網站、網站設計、企業(yè)官網、英文網站、手機端網站、網站推廣、國際域名空間、網站空間、企業(yè)郵箱。業(yè)務覆蓋朔州地區(qū)。

Java中PriorityQueue通過二叉小頂堆實現(xiàn)，可以用一棵完全二叉樹表示。本文從Queue接口函數出發(fā)，結合生動的圖解，深入淺出地分析PriorityQueue每個操作的具體過程和時間復雜度，將讓讀者建立對PriorityQueue建立清晰而深入的認識。

總體介紹

前面以JavaArrayDeque為例講解了Stack和Queue，其實還有一種特殊的隊列叫做PriorityQueue，即優(yōu)先隊列。優(yōu)先隊列的作用是能保證每次取出的元素都是隊列中權值最小的（Java的優(yōu)先隊列每次取最小元素，C++的優(yōu)先隊列每次取較大元素）。這里牽涉到了大小關系，元素大小的評判可以通過元素本身的自然順序（natural ordering），也可以通過構造時傳入的比較器（Comparator，類似于C++的仿函數）。

Java中PriorityQueue實現(xiàn)了Queue接口，不允許放入null元素；其通過堆實現(xiàn)，具體說是通過完全二叉樹（complete binary tree）實現(xiàn)的小頂堆（任意一個非葉子節(jié)點的權值，都不大于其左右子節(jié)點的權值），也就意味著可以通過數組來作為PriorityQueue的底層實現(xiàn)。

上圖中我們給每個元素按照層序遍歷的方式進行了編號，如果你足夠細心，會發(fā)現(xiàn)父節(jié)點和子節(jié)點的編號是有聯(lián)系的，更確切的說父子節(jié)點的編號之間有如下關系：

leftNo = parentNo*2+1

rightNo = parentNo*2+2

parentNo = (nodeNo-1)/2

通過上述三個公式，可以輕易計算出某個節(jié)點的父節(jié)點以及子節(jié)點的下標。這也就是為什么可以直接用數組來存儲堆的原因。

PriorityQueue的peek()和element操作是常數時間，add(),offer(), 無參數的remove()以及poll()方法的時間復雜度都是log(N)。

方法剖析

add()和offer()

add(E e)和offer(E e)的語義相同，都是向優(yōu)先隊列中插入元素，只是Queue接口規(guī)定二者對插入失敗時的處理不同，前者在插入失敗時拋出異常，后則則會返回false。對于PriorityQueue這兩個方法其實沒什么差別。

新加入的元素可能會破壞小頂堆的性質，因此需要進行必要的調整。

//offer(E e)
public boolean offer(E e) {
  if (e == null)//不允許放入null元素
    throw new NullPointerException();
  modCount++;
  int i = size;
  if (i >= queue.length)
    grow(i + 1);//自動擴容
  size = i + 1;
  if (i == 0)//隊列原來為空，這是插入的第一個元素
    queue[0] = e;
  else
    siftUp(i, e);//調整
  return true;
}

上述代碼中，擴容函數grow()類似于ArrayList里的grow()函數，就是再申請一個更大的數組，并將原數組的元素復制過去，這里不再贅述。需要注意的是siftUp(int k, E x)方法，該方法用于插入元素x并維持堆的特性。

//siftUp()
private void siftUp(int k, E x) {
  while (k > 0) {
    int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
    Object e = queue[parent];
    if (comparator.compare(x, (E) e) >= 0)//調用比較器的比較方法
      break;
    queue[k] = e;
    k = parent;
  }
  queue[k] = x;
}

新加入的元素x可能會破壞小頂堆的性質，因此需要進行調整。調整的過程為：從k指定的位置開始，將x逐層與當前點的parent進行比較并交換，直到滿足x >= queue[parent]為止。注意這里的比較可以是元素的自然順序，也可以是依靠比較器的順序。

element()和peek()

element()和peek()的語義完全相同，都是獲取但不刪除隊首元素，也就是隊列中權值最小的那個元素，二者的區(qū)別是當方法失敗時前者拋出異常，后者返回null。根據小頂堆的性質，堆頂那個元素就是全局最小的那個；由于堆用數組表示，根據下標關系，0下標處的那個元素既是堆頂元素。所以直接返回數組0下標處的那個元素即可。

代碼也就非常簡潔：

//peek()
public E peek() {
  if (size == 0)
    return null;
  return (E) queue[0];//0下標處的那個元素就是最小的那個
}

remove()和poll()

remove()和poll()方法的語義也完全相同，都是獲取并刪除隊首元素，區(qū)別是當方法失敗時前者拋出異常，后者返回null。由于刪除操作會改變隊列的結構，為維護小頂堆的性質，需要進行必要的調整。

代碼如下：

public E poll() {
  if (size == 0)
    return null;
  int s = --size;
  modCount++;
  E result = (E) queue[0];//0下標處的那個元素就是最小的那個
  E x = (E) queue[s];
  queue[s] = null;
  if (s != 0)
    siftDown(0, x);//調整
  return result;
}

上述代碼首先記錄0下標處的元素，并用最后一個元素替換0下標位置的元素，之后調用siftDown()方法對堆進行調整，最后返回原來0下標處的那個元素（也就是最小的那個元素）。重點是siftDown(int k, E x)方法，該方法的作用是從k指定的位置開始，將x逐層向下與當前點的左右孩子中較小的那個交換，直到x小于或等于左右孩子中的任何一個為止。

//siftDown()
private void siftDown(int k, E x) {
  int half = size >>> 1;
  while (k < half) {
    //首先找到左右孩子中較小的那個，記錄到c里，并用child記錄其下標
    int child = (k << 1) + 1;//leftNo = parentNo*2+1
    Object c = queue[child];
    int right = child + 1;
    if (right < size &&
      comparator.compare((E) c, (E) queue[right]) > 0)
      c = queue[child = right];
    if (comparator.compare(x, (E) c) <= 0)
      break;
    queue[k] = c;//然后用c取代原來的值
    k = child;
  }
  queue[k] = x;
}

remove(Object o)

remove(Object o)方法用于刪除隊列中跟o相等的某一個元素（如果有多個相等，只刪除一個），該方法不是Queue接口內的方法，而是Collection接口的方法。由于刪除操作會改變隊列結構，所以要進行調整；又由于刪除元素的位置可能是任意的，所以調整過程比其它函數稍加繁瑣。具體來說，remove(Object o)可以分為2種情況：1. 刪除的是最后一個元素。直接刪除即可，不需要調整。2. 刪除的不是最后一個元素，從刪除點開始以最后一個元素為參照調用一次siftDown()即可。此處不再贅述。

具體代碼如下：

//remove(Object o)
public boolean remove(Object o) {
  //通過遍歷數組的方式找到第一個滿足o.equals(queue[i])元素的下標
  int i = indexOf(o);
  if (i == -1)
    return false;
  int s = --size;
  if (s == i) //情況1
    queue[i] = null;
  else {
    E moved = (E) queue[s];
    queue[s] = null;
    siftDown(i, moved);//情況2
    ......
  }
  return true;
}

上述內容就是priorityqueue怎么在JAVA中使用，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

分享名稱：priorityqueue怎么在JAVA中使用-創(chuàng)新互聯(lián)
URL地址：http://chinadenli.net/article2/ghjoc.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供網頁設計公司、網站維護、用戶體驗、手機網站建設、虛擬主機、靜態(tài)網站

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)