優(yōu)先隊(duì)列是二叉堆的一個(gè)應(yīng)用，普通隊(duì)列的特點(diǎn)是先進(jìn)先出（FIFO）。優(yōu)先隊(duì)列不再遵循先入先出的原則，而是分為兩種情況：

最大優(yōu)先隊(duì)列，無論入隊(duì)順序，當(dāng)前最大的元素優(yōu)先出隊(duì)。

最小優(yōu)先隊(duì)列，無論入隊(duì)順序，當(dāng)前最小的元素優(yōu)先出隊(duì)。

比如有一個(gè)最大優(yōu)先隊(duì)列，它的最大元素是8，那么雖然元素8并不是隊(duì)首元素，但出隊(duì)的時(shí)候仍然讓元素8首先出隊(duì)：

什么是優(yōu)先隊(duì)列？

要滿足以上需求，利用線性數(shù)據(jù)結(jié)構(gòu)并非不能實(shí)現(xiàn)，但是時(shí)間復(fù)雜度較高，最壞時(shí)間復(fù)雜度O（n），并不是最理想的方式。而二叉堆卻很適合,二叉堆的特性：

1.最大堆的堆頂是整個(gè)堆中的最大元素

2.最小堆的堆頂是整個(gè)堆中的最小元素**

因此，我們可以用最大堆來實(shí)現(xiàn)最大優(yōu)先隊(duì)列，每一次入隊(duì)操作就是堆的插入操作，每一次出隊(duì)操作就是堆頂刪除操作。因而優(yōu)先隊(duì)列的入隊(duì)和出隊(duì)的時(shí)間復(fù)雜度均為log(n)

入隊(duì)操作

1.插入新節(jié)點(diǎn)5

什么是優(yōu)先隊(duì)列？

2.新節(jié)點(diǎn)5上浮到合適位置。

什么是優(yōu)先隊(duì)列？

出隊(duì)操作

1.把原堆頂節(jié)點(diǎn)10“出隊(duì)”

什么是優(yōu)先隊(duì)列？

2.最后一個(gè)節(jié)點(diǎn)1替換到堆頂位置

什么是優(yōu)先隊(duì)列？

3.節(jié)點(diǎn)1下沉，節(jié)點(diǎn)9成為新堆頂

什么是優(yōu)先隊(duì)列？

代碼實(shí)現(xiàn)

public class TestMain {
  public static void main(String[] args) {
    int[] a = new int[20];
    for (int i = 0; i < a.length; i++) {
      int temp = (int)(StdRandom.random()*100);
      a[i] = temp;
    }
    for (int i : a) {
      System.out.print(i+" ");
    }
    System.out.println();
    PQHeap pq = new PQHeap();
    for (int i = 0; i < 20; i++) {
      pq.insert(a[i]);
    }
    System.out.println();
    for (int i = 0; i < 20; i++) {
      System.out.print(pq.delMax()+" ");
    }
  }
}
/*
 * 優(yōu)先隊(duì)列的堆實(shí)現(xiàn)
 * 二叉堆，每個(gè)元素有兩個(gè)子元素，兩個(gè)子元素均比自己小
 */
class PQHeap{
  private int[] a;
  private int p = 1;
  public PQHeap() {
    a = new int[2];
  }
  /*
   * 插入元素
   */
  public void insert(int elements) {
    if (p == a.length) { resize(a.length*2); }
    a[p++] = elements;
    swim(p - 1); //將剛插入的元素上浮到正確位置
  }
  /*
   * 返回并刪除最大元素
   */
  public int delMax() {
    if (p == a.length/4) { resize(a.length/2); }
    int result = a[1]; //找出最大元素
    exch(1, --p); //將最后一個(gè)元素移到頂端
    a[p] = 0; 
    sink(1); //將剛移上去的元素沉下去，使堆有序
    return result;
  }
  public boolean isEmpty() {
    return p == 0;
  }
  public int size() {
    return p;
  }
  public void show() {
    for (int i : a) {
      System.out.print(i+" ");
    }
    System.out.println();
  }
  /*
   * 上浮元素
   */
  private void swim(int k) { //將元素與父元素比較，比父元素大則換位置
    while (k > 1 && a[k/2] < a[k]) { 
      exch(k/2, k);
      k = k/2;
    }
  }
  private void sink(int k) { //將元素與子元素比較，比子元素小則和兩個(gè)中較大的那個(gè)換位置
    while (2*k < p && (a[k] < a[2*k + 1]) || (a[k] < a[2*k])) {
      if (a[2*k + 1] > a[2*k]) { exch(k, 2*k + 1); k = 2*k + 1; }
      else           { exch(k, 2*k); k = 2*k; }
    }
  }
  private void resize(int length) {
    int[] b = new int[length]; //將數(shù)組長度改變
    for (int i = 0; i < p; i++) { //將數(shù)組復(fù)制
      b[i] = a[i];
    }
    a = b; //讓a指向b的內(nèi)存空間
  }
  /*
   * 交換
   */
  private void exch (int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
  }
}