二叉堆定義

二叉堆是一種特殊的堆, 二叉堆是完全二叉樹或者近似完全二叉樹. 二叉堆滿足堆特性: 父節(jié)點的鍵值總是保持固定的序關(guān)系于任何一個子節(jié)點的鍵值(就是父節(jié)點大/小于子節(jié)點), 且每個節(jié)點的左子樹和右子樹都是一個二叉堆.
當(dāng)父節(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值時為最大二叉堆. 當(dāng)父節(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值時為最小堆

二叉堆的表現(xiàn)形式

二叉堆一般用數(shù)組來表示. 如果節(jié)點在數(shù)組中的位置是n(n是節(jié)點在數(shù)組中的下標(biāo)), 則n節(jié)點對應(yīng)的子節(jié)點在數(shù)組中的位置分別是 2n + 1 和 2n + 2. 因此, 第1個位置的子節(jié)點在2和3, 第2個位置的子節(jié)點在4和5, 以此類推.

如下圖, 左圖是最小堆, 右圖是最大堆

        1                         11
      /   \                      /  \
     2     3                   9     10
    /  \  /  \                / \   /  \
   4   5  6  7               5  6  7   8
  /\   /\                   /\  /\
 8  9 10 11                1 2 3  4 

而將這兩個堆保存在數(shù)組中:

左圖:  1  2  3  4  5  6  7  8  9 10 11
右圖: 11  9 10  5  6  7  8  1  2  3  4

明白了堆的特性以及存儲方式, 那我們就能推斷出:

1. parent(t) = (t - 1) >>>1 (t指數(shù)組中的下標(biāo), >>> 或 <<< 表示數(shù)據(jù)在進(jìn)行無符號的左右移動, 每移動一位就等于整除2)
2. left(t) = t << 1 + 1
3. right(t) = t << 1 + 2

注意:
parent(t): 指t節(jié)點的父節(jié)點在數(shù)組中的下標(biāo)
left(t): 指t節(jié)點的左子節(jié)點在數(shù)組中的下標(biāo)
right(t): 指t節(jié)點的右子節(jié)點在數(shù)組中的下標(biāo)

基本操作

二叉堆的基本操作: 插入元素, 刪除元素, 堆排序, 堆向上調(diào)整(siftUp), 堆向下調(diào)整(siftDown)

插入元素

/**
 * 插入元素到堆中
 * @param e
 * @return
 * @throws InterruptedException
 */
public boolean put(E e) throws InterruptedException{
    lock.lockInterruptibly();
    try {
        if(e == null) throw new NullPointerException();
        // 1. 判斷堆是否滿了, 滿了的話就等待, 直到有其他線程拿走元素
        if(size > queues.length){ // queue已經(jīng)滿了, 等待清楚
            notFull.await(); // 這個 await 是響應(yīng)線程中斷的
        }
        // 2. 若堆中沒有元素, 則直接在堆的頭節(jié)點放入元素
        if(size == 0){ // heap中沒有數(shù)據(jù)
            queues[0] = e;
        }else{
            queues[size] = e;
            size++;
            siftUp(size - 1, e);
        }
        notEmpty.signal();
    } finally {
        lock.unlock();
    }
    return true;
}

插入:

1. 若heap沒數(shù)據(jù)則直接將元素放置頭節(jié)點, ok
2. 若heap有元素, 則將元素放置到為節(jié)點, 在調(diào)用 siftUp 進(jìn)行heap調(diào)整(那什么是 siftUp 調(diào)整呢, 我們接下來看)

向上調(diào)整

/**在數(shù)組中插入元素x到下標(biāo)為k的位置, 為保持堆的性質(zhì),
 * 通過siftUp來進(jìn)行調(diào)整, 直到x大于或等于x的 parent的值或到root節(jié)點
 *
 * @param k
 * @param x
 */
private void siftUp(int k, E x){
    Comparable<? super E> key = (Comparable<? super E>)x;
    while(k > 0){
        int parent = parent(k);  // 獲取對應(yīng)的父節(jié)點的下標(biāo)
        Object e = queues[parent]; // 獲取對應(yīng)的父節(jié)點對應(yīng)的值
        // 將當(dāng)前節(jié)點與父節(jié)點的值進(jìn)行比較
        // 若當(dāng)前節(jié)點比其父節(jié)點大, 則說明不在需要在向上 sift 比較了
        //
        if(key.compareTo((E) e) >= 0){
            break;
        }
        queues[k] = e; // 將父節(jié)點下沉
        k = parent; // 將這次比較的父節(jié)點賦值給k, 為下次 k 與其父節(jié)點作比較而準(zhǔn)備
    }
    // 這里的k 有可能是最初節(jié)點 x的父節(jié)點, 也有可能就是x節(jié)點父節(jié)點的下標(biāo)
    queues[k] = key;
}

siftUp:
整個邏輯比較簡單: 將當(dāng)前節(jié)點與父節(jié)點進(jìn)行比較, 不滿足堆特性的進(jìn)行調(diào)整, 直到滿足為止

刪除元素

/**
 * 獲取隊列中的頭節(jié)點
 * @return
 * @throws InterruptedException
 */
public E take() throws InterruptedException{

    /**
     * 1. 直接將頭節(jié)點獲取
     * 2. 將隊列中的尾節(jié)點拿出來, 從節(jié)點0開始siftdown -> 調(diào)整heap,使得,這個堆的最小值還在heap的頂上
     */
    E result = null;
    lock.lockInterruptibly();
    try {
        // 1. 若heap為空, 則等待, 直到有數(shù)據(jù)
        if(size == 0){ // heap中沒數(shù)據(jù)
            notEmpty.await(); // 等待放入數(shù)據(jù)
            return null;
        }
        int s = size - 1;
        // 2. 將heap的頭節(jié)點拿出來
        result = (E)queues[0];
        // 3. 將heap的尾節(jié)點拿出來, 若堆中還有元素, 在從(index=0)從開始siftdown調(diào)整堆
        E x = (E)queues[s];
        queues[s] = null;
        if(s != 0){
            siftDown(0, x);
        }
        size--;
        notFull.signal(); // 進(jìn)行喚醒
    } finally {
        lock.unlock();
    }
    return result;
}

刪除元素:

1. 直接將頭節(jié)點獲取
2. 將隊列中的尾節(jié)點拿出來, 從節(jié)點0開始siftdown -> 調(diào)整heap,使得,這個堆的最小值還在heap的頂上,那什么是siftDown, 我們接著看(其實和siftUp差不多)

堆向下調(diào)整

/**
 * 插入元素x到位置k, 為保持二叉堆的特性, 對x進(jìn)行siftDown, 直到x<=子節(jié)點
 * @param k
 * @param x
 */
private void siftDown(int k, E x){
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = parent(size -1); // 最后一個節(jié)點的父節(jié)點下標(biāo)
    while(k < half){
        // 1. 獲取子節(jié)點的坐標(biāo), 并取出兩者中的最小值
        int child = leftChildIndex(k);
        Object c = queues[child];
        int right = child + 1;

        // 2. 選中子節(jié)點中最小的那個節(jié)點進(jìn)行比較
        if(right < size -1 ){
            Object r = queues[right];
            if(((E)c).compareTo((E)r) >= 1) {
                c = queues[child = right];
            }
        }
        // 3. 若節(jié)點小于子節(jié)點, 則比較結(jié)束
        if(key.compareTo((E) c) <= 0){
            break;
        }
        queues[k] = c; // 將子節(jié)點上行
        k = child; // 父節(jié)點的光標(biāo)下移, 為下次比較準(zhǔn)備
    }
    queues[k] = key;
}

siftDown:整個邏輯比較簡單: 將當(dāng)前節(jié)點子節(jié)點進(jìn)行比較, 不滿足堆特性的進(jìn)行調(diào)整, 直到滿足為止

最后貼上上面代碼的完整版本 Heap.java

總結(jié):
二叉堆在java的運用比較廣, 如PriorityQueue, DelayQueue內(nèi)部實現(xiàn)都是基于二叉堆; 而難的地方個人覺得在主要在于堆的調(diào)整

1. 元素進(jìn)行插入時, 直接插入到尾節(jié)點, 再將尾節(jié)點進(jìn)行向上調(diào)整, 直到根節(jié)點(整個調(diào)整其實就是swap值, 將最大/小放到根節(jié)點)
2. 刪除元素時, 將尾元素放置到頭節(jié)點, 開始向下調(diào)整

參考資料:
vickyqi寫的Heap.java
skywang12345寫的二叉堆