【戀上數(shù)據(jù)結(jié)構(gòu)與算法一】(十四)二叉堆

思考

?設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，用來(lái)存放整數(shù)，要求提供 3 個(gè)接口
添加元素
獲取最大值
刪除最大值

? 有沒(méi)有更優(yōu)的數(shù)據(jù)結(jié)構(gòu)?
堆
? 獲取最大值:O(1)、刪除最大值:O(logn)、添加元素:O(logn)

Top K問(wèn)題

?什么是 Top K 問(wèn)題
從海量數(shù)據(jù)中找出前 K 個(gè)數(shù)據(jù)

?比如
從 100 萬(wàn)個(gè)整數(shù)中找出最大的 100 個(gè)整數(shù)

?Top K 問(wèn)題的解法之一:可以用數(shù)據(jù)結(jié)構(gòu)“堆”來(lái)解決

堆(Heap)

? 堆(Heap)也是一種樹(shù)狀的數(shù)據(jù)結(jié)構(gòu)(不要跟內(nèi)存模型中的“堆空間”混淆)，常見(jiàn)的堆實(shí)現(xiàn)有
1、二叉堆(Binary Heap，完全二叉堆)
2、多叉堆(D-heap、D-ary Heap)
3、索引堆(Index Heap)
4、二項(xiàng)堆(Binomial Heap)
5、斐波那契堆(Fibonacci Heap)
6、左傾堆(Leftist Heap，左式堆)
7、斜堆(Skew Heap)

?堆的一個(gè)重要性質(zhì):任意節(jié)點(diǎn)的值總是 ≥( ≤ )子節(jié)點(diǎn)的值
如果任意節(jié)點(diǎn)的值總是 ≥ 子節(jié)點(diǎn)的值，稱(chēng)為:最大堆、大根堆、大頂堆
如果任意節(jié)點(diǎn)的值總是 ≤ 子節(jié)點(diǎn)的值，稱(chēng)為:最小堆、小根堆、小頂堆

? 由此可見(jiàn)，堆中的元素必須具備可比較性(跟二叉搜索樹(shù)一樣)

堆的基本接口設(shè)計(jì)

int size();            // 元素的數(shù)量
boolean isEmpty();     // 是否為空
void clear();          // 清空
void add(E element);   // 添加元素
E get();               // 獲得堆頂元素
E remove();            // 刪除堆頂元素
E replace(E element);  // 刪除堆頂元素的同時(shí)插入一個(gè)新元素

二叉堆(Binary Heap)

? 二叉堆的邏輯結(jié)構(gòu)就是一棵完全二叉樹(shù)，所以也叫完全二叉堆

? 鑒于完全二叉樹(shù)的一些特性，二叉堆的底層(物理結(jié)構(gòu))一般用數(shù)組實(shí)現(xiàn)即可

? 索引 i 的規(guī)律( n 是元素?cái)?shù)量)
如果 i = 0 ，它是根節(jié)點(diǎn)

如果 i > 0 ，它的父節(jié)點(diǎn)的索引為 floor( (i – 1) / 2 ) （向下取整）

如果 2i + 1 ≤ n – 1，它的左子節(jié)點(diǎn)的索引為 2i + 1
如果 2i + 1 > n – 1 ，它無(wú)左子節(jié)點(diǎn)

如果 2i + 2 ≤ n – 1 ，它的右子節(jié)點(diǎn)的索引為 2i + 2
如果 2i + 2 > n – 1 ，它無(wú)右子節(jié)點(diǎn)

獲取最大值

最大堆 – 添加

最大堆 – 添加 – 總結(jié)

?循環(huán)執(zhí)行以下操作(圖中的 80 簡(jiǎn)稱(chēng)為 node)
如果 node > 父節(jié)點(diǎn)
? 與父節(jié)點(diǎn)交換位置

如果 node ≤ 父節(jié)點(diǎn)，或者 node 沒(méi)有父節(jié)點(diǎn)
? 退出循環(huán)

?這個(gè)過(guò)程，叫做上濾(Sift Up)
時(shí)間復(fù)雜度:O(logn)

最大堆 – 添加 – 交換位置的優(yōu)化

? 一般交換位置需要3行代碼，可以進(jìn)一步優(yōu)化
將新添加節(jié)點(diǎn)備份，確定最終位置才擺放上去

? 僅從交換位置的代碼角度看
可以由大概的 3 * O(logn) 優(yōu)化到 1 * O(logn) + 1

public void add(E element) {
    elementNotNullCheck(element);
    ensureCapacity(size + 1);
    elements[size++] = element;
    siftUp(size - 1);
}

private void elementNotNullCheck(E element) {
    if (element == null) {
        throw new IllegalArgumentException("element must not be null");
    }
}

// 擴(kuò)容
private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity) return;
    
    // 新容量為舊容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
}

/**
 * 讓index位置的元素上濾
 * @param index
 */
private void siftUp(int index) {
    
    E element = elements[index];// 添加的元素
    while (index > 0) {
        int parentIndex = (index - 1) >> 1;
        E parent = elements[parentIndex];
        if (compare(element, parent) <= 0) break;
        
        // 將父元素存儲(chǔ)在index位置
        elements[index] = parent;
        
        // 重新賦值index
        index = parentIndex;
    }
    elements[index] = element;
}

最大堆 – 刪除

最大堆 – 刪除 – 總結(jié)

  1. 用最后一個(gè)節(jié)點(diǎn)覆蓋根節(jié)點(diǎn)
  2. 刪除最后一個(gè)節(jié)點(diǎn)
  3. 循環(huán)執(zhí)行以下操作(圖中的43簡(jiǎn)稱(chēng)為node)
    如果 node < 最大的子節(jié)點(diǎn)
    ? 與最大的子節(jié)點(diǎn)交換位置

如果 node ≥ 最大的子節(jié)點(diǎn)， 或者 node 沒(méi)有子節(jié)點(diǎn)
? 退出循環(huán)

?這個(gè)過(guò)程，叫做下濾(Sift Down)，時(shí)間復(fù)雜度:O(logn)

? 同樣的，交換位置的操作可以像添加那樣進(jìn)行優(yōu)化

最大堆 – 刪除

@Override
public E remove() {
    emptyCheck();
    
    int lastIndex = --size;
    E root = elements[0];
    elements[0] = elements[lastIndex];
    elements[lastIndex] = null;
    
    siftDown(0);
    return root;
}

private void emptyCheck() {
    if (size == 0) {
        throw new IndexOutOfBoundsException("Heap is empty");
    }
}

/**
 * 讓index位置的元素下濾
 * @param index
 */
private void siftDown(int index) {
    E element = elements[index];
    int half = size >> 1;
    // 第一個(gè)葉子節(jié)點(diǎn)的索引 == 非葉子節(jié)點(diǎn)的數(shù)量
    // index < 第一個(gè)葉子節(jié)點(diǎn)的索引
    // 必須保證index位置是非葉子節(jié)點(diǎn)
    while (index < half) {
        // index的節(jié)點(diǎn)有2種情況
        // 1.只有左子節(jié)點(diǎn)
        // 2.同時(shí)有左右子節(jié)點(diǎn)
        
        // 默認(rèn)為左子節(jié)點(diǎn)跟它進(jìn)行比較
        int childIndex = (index << 1) + 1;
        E child = elements[childIndex];
        
        // 右子節(jié)點(diǎn)
        int rightIndex = childIndex + 1;
        
        // 選出左右子節(jié)點(diǎn)最大的那個(gè)
        if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
            child = elements[childIndex = rightIndex];
        }
        
        if (compare(element, child) >= 0) break;

        // 將子節(jié)點(diǎn)存放到index位置
        elements[index] = child;
        // 重新設(shè)置index
        index = childIndex;
    }
    elements[index] = element;
}

replace

// 刪除堆頂元素的同時(shí)插入一個(gè)新元素
@Override
public E replace(E element) {
    elementNotNullCheck(element);
    
    E root = null;
    if (size == 0) {
        elements[0] = element;
        size++;
    } else {
        root = elements[0];
        elements[0] = element;
        siftDown(0);
    }
    return root;
}

最大堆 – 批量建堆(Heapify)

?批量建堆，有 2 種做法
自上而下的上濾
自下而上的下濾

最大堆 – 批量建堆 – 自上而下的上濾

最大堆 – 批量建堆 – 自上而下的下濾

最大堆 – 批量建堆 – 效率對(duì)比

? 所有節(jié)點(diǎn)的深度之和
僅僅是葉子節(jié)點(diǎn)，就有近 n/2 個(gè)，而且每一個(gè)葉子節(jié)點(diǎn)的深度都是 O(logn) 級(jí)別的
因此，在葉子節(jié)點(diǎn)這一塊，就達(dá)到了 O(nlogn) 級(jí)別
O(nlogn) 的時(shí)間復(fù)雜度足以利用排序算法對(duì)所有節(jié)點(diǎn)進(jìn)行全排序

? 所有節(jié)點(diǎn)的高度之和
假設(shè)是滿樹(shù)，節(jié)點(diǎn)總個(gè)數(shù)為 n，樹(shù)高為 h，那么 n = 2h ? 1
所有節(jié)點(diǎn)的樹(shù)高之和：
H(n) = 20 ? (h?0) +21 ? (h?1) +22 ? (h?2) +?+2h?1 ?[h? (h?1)]
H(n) = h? (20+21+22+?+2h?1 )? [1?21+2?22+3?23+?+ (h?1)?2h?1]
H(n) = h? (2h ?1) ? [(h?2)?2h+2]
H(n) = h?2^h ?h?h?2h +2h+1 ?2
H(n) = 2h+1 ?h?2 = 2?(2h ?1)?h
H(n) = 2n ?h
H(n) = 2n?log2(n+1)
H(n) = O(n)

公式推導(dǎo)

?S(h) = 1?21 +2?22 +3?23 +?+ (h?2) ?2h?2 + (h?1) ?2h?1

?2S(h)=1?22+2?23+3?24+?+ (h?2) ?2h?1+ (h?1) ?2h

?S(h)–2S(h)=[21+22+23+?+2h?1^]? (h?1) ?2h=(2h?2)? (h?1) ?2h

?S(h) = (h?1) ?2h ?(2h ?2) = (h?2) ?2h +2

疑惑

? 以下方法可以批量建堆么
自上而下的下濾
自下而上的上濾

? 上述方法不可行，為什么?
認(rèn)真思考【自上而下的上濾】、【自下而上的下濾】的本質(zhì)

批量建堆

public BinaryHeap(E[] elements, Comparator<E> comparator)  {
    super(comparator);
    
    if (elements == null || elements.length == 0) {
        this.elements = (E[]) new Object[DEFAULT_CAPACITY];
    } else {
        size = elements.length;
        int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
        this.elements = (E[]) new Object[capacity];
        for (int i = 0; i < elements.length; i++) {
            this.elements[i] = elements[i];
        }
        heapify();
    }
}

/**
 * 批量建堆
 */
private void heapify() {
    // 自上而下的上濾
//    for (int i = 1; i < size; i++) {
//        siftUp(i);
//    }
    
    // 自下而上的下濾 - 效率高
    for (int i = (size >> 1) - 1; i >= 0; i--) {
        siftDown(i);
    }
}

如何構(gòu)建一個(gè)小頂堆?

static void test() {
    System.out.println("------------------------------------- 最小堆");
    Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
    BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
        // 修改比較策略即可
        public int compare(Integer o1, Integer o2) {
//            return o1 - o2;// 最大堆
            return o2 - o1;// 最小堆
        }
    });
    BinaryTrees.println(heap);
}

Top K問(wèn)題

?從 n 個(gè)整數(shù)中，找出最大的前 k 個(gè)數(shù)( k 遠(yuǎn)遠(yuǎn)小于 n )

?如果使用排序算法進(jìn)行全排序，需要 O(nlogn) 的時(shí)間復(fù)雜度

?如果使用二叉堆來(lái)解決，可以使用 O(nlogk) 的時(shí)間復(fù)雜度來(lái)解決
新建一個(gè)小頂堆
掃描 n 個(gè)整數(shù)
?先將遍歷到的前 k 個(gè)數(shù)放入堆中
?從第 k + 1 個(gè)數(shù)開(kāi)始，如果大于堆頂元素，就使用 replace 操作(刪除堆頂元素，將第 k + 1 個(gè)數(shù)添加到堆中)
掃描完畢后，堆中剩下的就是最大的前 k 個(gè)數(shù)

static void test() {
    
    System.out.println("------------------------------------- Top K問(wèn)題");
    
    // 新建一個(gè)小頂堆
    BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
    
    // 找出最大的前k個(gè)數(shù)
    int k = 3;
    
    Integer[] data = {51, 30, 39, 92, 74, 25, 16, 93,
            91, 19, 54, 47, 73, 62, 76, 63, 35, 18,
            90, 6, 65, 49, 3, 26, 61, 21, 48};
    for (int i = 0; i < data.length; i++) {
        if (heap.size() < k) { // 前k個(gè)數(shù)添加到小頂堆
            heap.add(data[i]); // logk
        } else if (data[i] > heap.get()) { // 如果是第k + 1個(gè)數(shù)，并且大于堆頂元素
            heap.replace(data[i]); // logk
        }
    }
    // O(nlogk)
    BinaryTrees.println(heap);
}

?如果是找出最小的前 k 個(gè)數(shù)呢?
用大頂堆
如果小于堆頂元素，就使用 replace 操作


static void test7() {
    
    System.out.println("------------------------------------- Top K問(wèn)題");
    
    // 新建一個(gè)小頂堆
    BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    });
    
    // 找出最小的前k個(gè)數(shù)
    int k = 3;
    
    Integer[] data = {51, 30, 39, 92, 74, 25, 16, 93,
            91, 19, 54, 47, 73, 62, 76, 63, 35, 18,
            90, 6, 65, 49, 3, 26, 61, 21, 48};
    for (int i = 0; i < data.length; i++) {
        if (heap.size() < k) { // 前k個(gè)數(shù)添加到小頂堆
            heap.add(data[i]); // logk
        } else if (data[i] < heap.get()) { // 如果是第k + 1個(gè)數(shù)，并且小于堆頂元素
            heap.replace(data[i]); // logk
        }
    }
    
    // O(nlogk)
    BinaryTrees.println(heap);
}

作業(yè)

? 了解和實(shí)現(xiàn)堆排序

? 使用堆排序?qū)⒁粋€(gè)無(wú)序數(shù)組轉(zhuǎn)換成一個(gè)升序數(shù)組
空間復(fù)雜度能否下降至 O(1)?

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容