前言

今日份的內(nèi)容很簡單，看官可以放心食用夯巷。

二叉堆

這一部分完全是大學(xué)數(shù)據(jù)結(jié)構(gòu)課程的復(fù)習(xí)赛惩。

性質(zhì)

顧名思義，二叉堆（binary heap）就是以二叉樹形式存在的堆數(shù)據(jù)結(jié)構(gòu)鞭莽，也是最簡單的堆坊秸。它是由J. Williams在1964年與堆排序算法一同提出的。二叉堆具有以下兩個基本性質(zhì)：

• 是一棵完全二叉樹澎怒；
• 每個節(jié)點存儲的值要么都小于等于它們的子節(jié)點的值，要么都大于等于它們的子節(jié)點的值阶牍。這兩種分別稱為最小堆（min-heap）和最大堆（max-heap）喷面。

下面的圖分別示出由同一個整數(shù)序列構(gòu)造出的最小堆和最大堆。

基本操作

二叉堆有兩種基本操作：插入（insert/sift-up）和彈出堆頂元素（extract/sift-down）走孽，在操作的過程中惧辈，需要時刻對堆進行調(diào)整，以使它總滿足堆的性質(zhì)磕瓷。

先來看插入操作盒齿，假設(shè)我們要在上圖所示的最大堆中插入元素48：

將48插入堆下層最左側(cè)的空閑位置念逞，由于48比父節(jié)點25大，不滿足堆性質(zhì)边翁，故要將48和25的位置交換翎承。交換后，48仍然比父節(jié)點36大符匾，需要再次交換叨咖。兩次交換之后，結(jié)果滿足堆性質(zhì)啊胶，插入結(jié)束甸各。可見焰坪，新節(jié)點在插入過程中是逐漸上浮的趣倾，所以也被稱作sift-up。

然后來看彈出堆頂元素操作某饰。取出堆頂元素（即堆內(nèi)的最大值或最小值）后儒恋，要將堆下層最右側(cè)的元素補到堆頂。

如圖所示露乏，7在堆頂不滿足最大堆的性質(zhì)碧浊，它的子節(jié)點中36較大，故要將7和36的位置交換瘟仿。交換后箱锐，子節(jié)點25仍然比7大，需要再次交換劳较，此時結(jié)果又滿足了堆性質(zhì)驹止。可見观蜗，彈出堆頂元素后對堆的調(diào)整操作實際上是節(jié)點逐漸下降的過程臊恋，所以也被稱作sift-down。

顯然墓捻，在極端情況下抖仅，一個節(jié)點會被sift-up到樹的最高層，或者被sift-down到樹的最底層砖第，故插入和彈出操作的最壞時間復(fù)雜度都是O(logN)撤卢。

存儲

我們已經(jīng)知道，完全二叉樹可以很方便地用數(shù)組存儲梧兼，所以二叉堆也一樣放吩。下圖示出一棵有7個節(jié)點的完全（滿）二叉樹的數(shù)組存儲。

也就是說羽杰，如果下標(biāo)從0開始的話渡紫，那么對于二叉堆內(nèi)下標(biāo)為i的任意節(jié)點到推，有：

• 它的子節(jié)點下標(biāo)分別為(2i + 1)和(2i + 2)；
• 它的父節(jié)點下標(biāo)為floor[(i - 1) / 2]惕澎。

由于數(shù)組占用的是連續(xù)的物理內(nèi)存莉测，當(dāng)堆的大小非常大并且系統(tǒng)啟用虛擬內(nèi)存時，就會被分散到許多內(nèi)存頁上存儲集灌，效率降低悔雹。B堆（B-heap）可以解決這個問題，詳情參考這里欣喧。

二叉堆的最主要應(yīng)用就是實現(xiàn)優(yōu)先隊列腌零，下面來看。

優(yōu)先隊列

顧名思義唆阿，優(yōu)先隊列（priority queue）也是一種隊列益涧，一端進一端出。與普通隊列的先進先出（FIFO）不同的是驯鳖，優(yōu)先隊列中的每個元素都有一個與之相關(guān)的優(yōu)先級闲询，當(dāng)執(zhí)行出隊操作時，彈出的是優(yōu)先級最高的那個元素浅辙。一般來講扭弧，優(yōu)先級就是元素結(jié)構(gòu)中的某個鍵值，如果鍵值小的元素優(yōu)先級高记舆，那么該隊列就是升序優(yōu)先隊列鸽捻；如果鍵值大的元素優(yōu)先級高，那么該隊列就是降序優(yōu)先隊列泽腮。從這個性質(zhì)可以看出御蒲，二叉堆特別用來適合實現(xiàn)優(yōu)先隊列：升序?qū)?yīng)最小堆，降序?qū)?yīng)最大堆诊赊。

多種編程語言都內(nèi)置了優(yōu)先隊列的實現(xiàn)厚满，Java集合框架中的實現(xiàn)就是java.util.PriorityQueue，它另外還有一個適應(yīng)并發(fā)環(huán)境的線程安全的實現(xiàn)：java.util.concurrent.PriorityBlockingQueue碧磅。類圖如下所示碘箍。

下面來簡要分析一下PriorityQueue類的源碼。

成員變量

private static final int DEFAULT_INITIAL_CAPACITY = 11;
private transient Object[] queue;
private int size = 0;
private final Comparator<? super E> comparator;
private transient int modCount = 0;

• DEFAULT_INITIAL_CAPACITY：隊列的默認初始容量11鲸郊；
• queue：存儲隊列（堆）元素的數(shù)組敲街；
• size：隊列的大小严望；
• comparator：隊列元素鍵值的比較器。默認的二叉堆是最小堆逻恐；
• modCount：隊列發(fā)生結(jié)構(gòu)化修改的次數(shù)像吻。關(guān)于它的用途峻黍，見一周前寫的這篇文章。

構(gòu)造方法

PriorityQueue有多種構(gòu)造方法拨匆，如下圖所示（其中的int為初始容量）姆涩。

所有從集合產(chǎn)生優(yōu)先隊列的構(gòu)造方法最終都會調(diào)用以下的方法。

  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;
  }

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

  private void heapify() {
    for (int i = (size >>> 1) - 1; i >= 0; i--)
      siftDown(i, (E) queue[i]);
  }

heapify()方法的含義就是“堆化”惭每，亦即將傳入的集合整理成堆骨饿。siftDown()方法的源碼在后面有。

入隊操作

入隊操作有add()和offer()兩個方法實現(xiàn)台腥，前者只是簡單地代理了后者宏赘。

  public boolean add(E e) {
    return offer(e);
  }

  public boolean offer(E e) {
    if (e == 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;
  }

offer()方法首先對入隊元素判空并增加modCount。然后黎侈，如果隊列大小已經(jīng)到了queue數(shù)組的長度察署，調(diào)用grow()方法對數(shù)組擴容。最后調(diào)用siftUp()方法插入元素到堆中峻汉，并維護堆性質(zhì)贴汪。根據(jù)有無傳入比較器，siftUp()方法有兩種實現(xiàn)休吠，下面來看默認比較邏輯下的實現(xiàn)方法扳埂。

  private void siftUp(int k, E x) {
    if (comparator != null)
      siftUpUsingComparator(k, x);
    else
      siftUpComparable(k, x);
  }

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

siftUpComparable()方法會找到父節(jié)點的下標(biāo)，并調(diào)用compareTo()方法比較節(jié)點值的自然大小瘤礁。由于默認是最小堆阳懂，當(dāng)要插入的節(jié)點值比父節(jié)點小時，就迭代地交換它們的值蔚携，直到上浮到合適的位置希太。

出隊操作

出隊操作由poll()方法來實現(xiàn)。

  public E poll() {
    if (size == 0)
      return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
      siftDown(0, x);
    return result;
  }

可見確實是將隊列中的最后一個元素（即二叉堆中最右下角的元素）放到最前酝蜒，并調(diào)用siftDown()方法進行下沉誊辉。與siftUp()方法相似地，它也有兩種邏輯亡脑，仍然來看默認的比較邏輯堕澄。

  private void siftDown(int k, E x) {
    if (comparator != null)
      siftDownUsingComparator(k, x);
    else
      siftDownComparable(k, x);
  }

  @SuppressWarnings("unchecked")
  private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
      int child = (k << 1) + 1; // assume left child is least
      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;
  }

完全二叉樹還有一個性質(zhì)：如果樹一共有N個節(jié)點，那么葉子節(jié)點正好有floor[N / 2]個霉咨。siftDown()方法就用這個性質(zhì)來保證在當(dāng)前節(jié)點不是葉子節(jié)點的情況下來循環(huán)處理蛙紫。由于要保持最小堆，每次循環(huán)都會取得左途戒、右子節(jié)點中較小的那個值坑傅，如果子節(jié)點的值小于父節(jié)點的，則交換它們喷斋。

刪除操作

注意唁毒，這里的刪除指的是根據(jù)下標(biāo)刪除優(yōu)先隊列中的任意一個節(jié)點蒜茴。

  public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
      return false;
    else {
      removeAt(i);
      return true;
    }
  }

  private E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    if (s == i) // removed last element
      queue[i] = null;
    else {
      E moved = (E) queue[s];
      queue[s] = null;
      siftDown(i, moved);
      if (queue[i] == moved) {
        siftUp(i, moved);
        if (queue[i] != moved)
          return moved;
      }
    }
    return null;
  }

由于是從中間刪除的，所以在常規(guī)的sift-down操作之后浆西，如果發(fā)現(xiàn)補位元素的下標(biāo)并未發(fā)生變化粉私，說明（在默認情況下）它的左右子節(jié)點都比它大，所以還需要新一輪的sift-up操作近零。時間已經(jīng)很晚了诺核，所以這里就不畫圖了，看官稍微想一想就能理解久信。

查看隊頭元素操作

簡單粗暴窖杀。

  public E peek() {
    return (size == 0) ? null : (E) queue[0];
  }

擴容操作

最后來看看前面提到過的grow()方法，不復(fù)雜入篮。

  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);
  }

可見陈瘦，如果當(dāng)前隊列長度小于64，則擴容一倍潮售，反之則擴容一半痊项。接下來調(diào)用hugeCapacity()方法做溢出檢查，并用Arrays.copyOf()方法復(fù)制數(shù)組內(nèi)容酥诽，這與ArrayList的擴容是相同的了鞍泉。

用優(yōu)先隊列解決Top-N問題

優(yōu)先隊列是一種強有力的輔助工具，它可以單獨用肮帐，也可以配合哈夫曼生成樹咖驮、Prim算法、Dijkstra算法等以提高效率训枢，看官如果打過算法類競賽的話應(yīng)該深有體會托修。而在互聯(lián)網(wǎng)世界中，升序優(yōu)先隊列（最小堆）經(jīng)常用來解決Top-N問題恒界，即“取得所有帖子中閱讀量排名前N的帖子”睦刃、“取得所有商品中銷量排名前N的商品”等。

舉個栗子十酣，假設(shè)與商品銷量相關(guān)的POJO如下：

@Getter
@Setter
public class MerchandiseSales {
  private long id;
  private long quantity;
  private long price;
  // ...
}

那么我們就可以通過如下的方法很容易地得出銷量Top-N排行榜涩拙。

int topN = /*...*/;
PriorityQueue<MerchandiseSales> minHeap = new PriorityQueue(
  topN + 1,
  Comparator.comparingLong(MerchandiseSales::getQuantity)
);

List<MerchandiseSales> sales = /*...*/;
for (MerchandiseSales m : sales) {
  if (minHeap.size() < topN) {
    minHeap.offer(m);
  } else if (minHeap.peek().getQuantity() < m.getQuantity()) {
    minHeap.poll();
    minHeap.offer(m);
  }
}

List<Long> ranking = new ArrayList<>();
for (int k = 0; k < topN && !minHeap.isEmpty(); k++) {
  ranking.add(minHeap.poll().getId());
}

需要注意的是，ranking列表中保存的商品仍然是按銷量升序排列的耸采，也就是說在實際展示排行榜時兴泥，應(yīng)該從尾到頭取出結(jié)果。

The End

甚累虾宇，希望12點半能睡吧搓彻。

晚安~