完全二叉樹——二叉堆(BinaryHeap)

前言

優先隊列是允許至少下列兩種操作的資料結構：insert(插入)以及deleteMin(删除最小者)，其中deleteMin的工作是找出、傳回、并删除優先隊列中最小的元素。insert操作等價于enqueue(入隊)，而deleteMin則相當于dequeue(出隊)。

二叉堆的性質

二叉堆的使用對于優先隊列的實作相當普遍。二叉堆具有結構性和堆序性：

結構性質

堆是一棵被完全填滿的二叉樹，有可能的例外是在底層葉子上，葉子上的元素從左到右填入。這樣的樹稱為完全二叉樹。

根據完全二叉樹的性質，我們可以使用一個數組來表示而不需要使用鍊。該數組有一個位置0，可在進行堆的插入操作時避免多次的指派(《資料結構forJava版》)。

完全二叉樹——二叉堆(BinaryHeap)

對于數組中任一位置i上的元素，其左兒子在位置2i上，右兒子在左兒子後的節點(2i+1)上，它的父親則在位置i/2上。是以，這裡不需要鍊就可以很簡單的周遊該樹。

一個堆結構将由一個(Comparable對象的)數組和一個代表目前堆的大小的整數組成。

堆序性質

**在一個堆中，對于每一個節點X，X的父親中的關鍵字小于或等于X中的關鍵字，根節點除外(它沒有父親)。**根據堆序性質我們可以很容易的得出最小的元素一定在根上，是以快速找出最小元将會是件非常容易的事，并且隻需要花費常數時間。

完全二叉樹——二叉堆(BinaryHeap)

基本的堆操作

在對堆的操作中，無外乎是需要往堆中插入元素以及删除最小元素，但是所有的操作都需要保證始終保持堆序性質。

insert插入

為了将一個元素X插入到堆中，我們需要在下一個可用位置建立一個空穴，否則該堆将不是完全樹。如果X可以放在該空穴中而不破壞堆的序，那麼插入完成。否則，我們把空穴的父節點上的元素移入該空穴中，這樣，空穴就朝着根的方向上冒一步。繼續該過程直到X能被放入空穴中為止。

根據下圖，我們想要插入14，我們在堆的下一個可用位置建立一個空穴，由于将14插入空穴破壞了堆的序(空穴父親的關鍵字31大于14)，是以将31移入該空穴，空穴位置上移到原31位置，接着繼續比較現在空穴與其父節點，直到找到置入14的正确位置。

完全二叉樹——二叉堆(BinaryHeap)

堆的插入政策叫做上濾。新元素在堆中上濾直到找到正确的位置。代碼也很容易實作插入。

/**
     * 插入操作，需要上濾元素
     * 通過不斷比較空穴元素hole與其父元素的大小進行元素上濾
     */
    public void insert(T item){
        if(currentSize == array.length - 1){
            enlargeArray(array.length * 2 + 1);
        }
        int hole = ++currentSize;
        for(;hole > 1 && item.compareTo(array[hole/2]) < 0;hole /= 2){
            array[hole] = array[hole/2];
        }
        array[hole] = item;
    }

當進行元素插入時，由于我們是使用數組作為堆的元素存放，是以必須考慮數組越界問題，其中

currentSize

為數組此刻的最後一個元素的序号，當它大于數組長度時需要進行擴容。

我們通過

array[hole/2]

獲得節點的父節點，然後來更改堆的序，確定每一個結點的父親的關鍵字都要小于或等于該節點。

正常的一次交換操作需要執行三條指派語句，如果一個元素上濾d層，那麼由于交換而執行的指派次數就達到3d，而我們這裡的方法卻隻用到d+1次指派。

deleteMin删除最小元

deleteMin以類似插入的方式處理。找出最小元是容易的，困難之處是删除它。當删除一個最小元時，需要在根節點建立一個空穴。由于現在堆少了一個元素，是以堆中最後一個元素X必須移動到該堆的某個地方。如果X可以被放到空穴中，那麼deleteMin完成，不過這一般不太可能，是以我們将空穴的兩個兒子中較小者移入空穴，這樣空穴向下推了一層。重複該步驟直到X可以被放入空穴中。

在下圖中，我們删除了該堆的最小元13，是以13位置成了空穴，所有此時需要将堆的最後一個元素31移入該空穴，但是發現該空穴的左兒子14小于該元素，是以需要将該左兒子移入空穴，并且空穴下移，反複該操作，直到31被放入正确的位置。這種一般的政策叫做下濾。

完全二叉樹——二叉堆(BinaryHeap)

删除最小元的代碼如下：

/**
     * 删除最小元
     * 将堆中最後一個元素放在根節點
     * 然後進行元素下濾
     * @return
     */
    public T deleteMin(){
        if (isEmpty()){
            throw new NoSuchElementException();
        }
        T minItem = findMin();
        array[1] = array[currentSize];
        array[currentSize--] = null;
        percolateDown(1);
        return minItem;
    }

    /**
     * 元素下濾
     * 從根節點開始比較其左右兒子，找出最小的兒子與父親進行比較
     * 直到兩兒子的值都大于父親則結束循環
     * 最後将根節點的值放入最小的兒子處
     * @param hole
     */
    public void percolateDown(int hole){
        int child;
        T tmp = array[hole];
        for(;hole * 2 <= currentSize;hole = child){
            child = hole * 2;
            if(child != currentSize && array[child + 1].compareTo(array[child]) < 0){
                child++;
            }
            if(child != currentSize && array[child].compareTo(tmp) < 0){
                array[hole] = array[child];
            } else {
                break;
            }
        }
        array[hole] = tmp;
    }

由于我們必須保證節點不總存在兩個兒子，是以在第30行我們需要對節點的兒子進行大小比較，確定下濾元素總是流向較小的一方。

完整代碼

由于堆的插入和删除最小元的代碼已經在上面給出，是以下面的代碼段将省略這兩個方法的代碼。

/**
 * @author: zhangocean
 * @Date: 2018/10/19 13:19
 * Describe:
 */
public class BinaryHeap<T extends Comparable<? super T>> {

    private static final int DEFAULT_CAPACITY = 10;
    private int currentSize;
    private T[] array;

    public BinaryHeap() {
        this(DEFAULT_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    private BinaryHeap(int heapSize) {
        currentSize = 0;
        //不能使用泛型建立數組
        array = (T[]) new Comparable[heapSize + 1];
    }

    @SuppressWarnings("unchecked")
    public BinaryHeap(T[] items) {
        currentSize = items.length;
        array = (T[]) new Comparable[(currentSize + 2) * 11 / 10];
        int i = 1;
        for (T item : items) {
            array[i++] = item;
        }
        buildHeap();
    }

    /**
     * 建立堆序
     * 從葉子節點中最左邊的父節點開始進行元素下濾
     */
    private void buildHeap() {
        for (int i = currentSize / 2; i > 0; i--) {
            percolateDown(i);
        }
    }

    /**
     * 插入操作，需要上濾元素
     * 通過不斷比較空穴元素hole與其父元素的大小進行元素上濾
     */
    public void insert(T item) {
        ///插入代碼見上方
    }

    /**
     * 查找堆中最小的元素(即根上的元素)
     *
     * @return
     */
    public T findMin() {
        if (isEmpty()) {
            return null;
        }
        return array[1];
    }

    /**
     * 删除最小元
     * 将堆中最後一個元素放在根節點
     * 然後進行元素下濾
     *
     * @return
     */
    public T deleteMin() {
        ///删除最小元代碼見上方
    }

    /**
     * 元素下濾
     * 從根節點開始比較其左右兒子，找出最小的兒子與父親進行比較
     * 直到兩兒子的值都大于父親則結束循環
     * 最後将根節點的值放入最小的兒子處
     *
     * @param hole
     */
    public void percolateDown(int hole) {
        ///元素下濾代碼見上方
    }


    public boolean isEmpty() {
        return currentSize == 0;
    }

    public void makeEmpty() {
        currentSize = 0;
        for (int i = 0; i < array.length; i++) {
            array[i] = null;
        }
    }

    /**
     * 數組擴容
     */
    private void enlargeArray(int newArraySize) {
        T[] oldArray = array;
        array = (T[]) new Comparable[newArraySize];
        int i = 0;
        for (T item : oldArray) {
            array[i++] = item;
        }
    }

    public void printHeap() {
        for (T item : array) {
            System.out.print(item + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        BinaryHeap<Integer> heap = new BinaryHeap<Integer>();
        for (int i = 0; i < 20; i++) {
            heap.insert(i);
        }
        heap.printHeap();
        heap.deleteMin();
        heap.printHeap();
        heap.deleteMin();
        heap.deleteMin();
        heap.printHeap();
    }
}

輸出結果如下所示：

null 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 null null 
null 1 3 2 7 4 5 6 15 8 9 10 11 12 13 14 19 16 17 18 null null null 
null 3 4 5 7 9 11 6 15 8 17 10 18 12 13 14 19 16 null null null null null

總結

二叉堆對于優先隊列的實作相對較于普遍。
堆需要保持堆的序，即對于堆中每個節點X，X的父親中關鍵字小于或等于X中的關鍵字，當然啦根節點除外(它木有父親)。
二叉堆是一棵完全二叉樹，根據它的結構性可以用數組的方式來實作，而避免了鍊的使用。
由于是用數組來實作一棵樹結構，是以需要能夠對樹中節點進行比較，是以通過new Comparable 數組實作數組元素之間的比較。
堆的主要操作在于元素插入以及删除最小元，插入時先在最後一個節點的下一個位置建立一個空穴，然後試着将需要插入的元素放入，否則上濾元素。删除最小元則是移除根節點(不用說，它肯定最小)元素，根節點成為空穴，再将最後一個結點試着移入該空穴中，否則進行元素下濾操作。

更多文章請關注我的個人部落格：www.zhyocean.cn

完全二叉樹——二叉堆(BinaryHeap)

前言

二叉堆的性質

結構性質

堆序性質

基本的堆操作

insert插入

deleteMin删除最小元

完整代碼

總結

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器