一、關(guān)于堆

JDK1.8中的PriortyQueue（優(yōu)先級隊列）底層使用了堆的數(shù)據(jù)結(jié)構(gòu)，而堆實際就是在完全二叉樹的基礎(chǔ)之上進(jìn)行了一些元素的調(diào)整。

1.堆的概念

堆有最大堆和最小堆之分。
最大（最?。┒咽且豢妹恳粋€節(jié)點的元素都不小于（大于）其孩子（如果存在）的元素的樹。大堆是一棵完全二叉樹，同時也是一棵最大樹。小堆是一棵完全二叉樹，同時也是一棵最小樹。
注意： 堆中的任一子樹也是堆，即大堆的子樹也都是大堆，小堆亦是。

2.堆的性質(zhì)

堆中某個結(jié)點的值總是不大于或不小于其父結(jié)點的值
堆總是一顆完全二叉樹

3.堆的存儲方式

由堆的概念可知，堆是一顆完全二叉樹，因此可以層序的規(guī)則采用順序的方式來高效存儲。
注意：對于非完全二叉樹，則不適合使用順序方式進(jìn)行存儲，因為為了能夠還原二叉樹，空間中必須要能夠存儲空結(jié)點，就會導(dǎo)致空間利用率比較低

二、堆的創(chuàng)建

1.堆向下調(diào)整

對于給出的一個數(shù)據(jù)，如何將其創(chuàng)建為堆呢？例如下圖：

仔細(xì)觀察上圖后發(fā)現(xiàn)：根結(jié)點的左右子樹已經(jīng)完全滿足堆的性質(zhì)，因此只需將根結(jié)點向下調(diào)整好即可。
以小堆為例：

1.讓parent標(biāo)記需要調(diào)整的結(jié)點，child標(biāo)記parent的左孩子（注意：parent如果有孩子一定是先有左孩子）
2.如果parent的左孩子存在，即child<size，進(jìn)行如下操作，直到parent的左孩子不存在

parent右孩子是否存在，如果存在則找出左右孩子中較小的孩子，使用child進(jìn)行標(biāo)記
將parent與較小的孩子（也就是此時的child）比較，如果：

parent小于較小的孩子child，這個結(jié)點已經(jīng)調(diào)整
否則：將parent與child進(jìn)行交換，交換成功后，這時parent中大的元素已經(jīng)向下移動，可能會導(dǎo)致子樹不滿足堆的特性，就需要繼續(xù)向下調(diào)整，即parent=child,child=parent*2+1,然后循環(huán)起來

圖解如下：

代碼實現(xiàn)：

    private void shiftDown(int parent){
        //默認(rèn)讓child先標(biāo)記左孩子---因為：parent可能有左沒有右
        int child=parent*2+1;

        //while循環(huán)條件可以保證：parent的左孩子一定存在
        //             但是不能保證parent的右孩子是否存在
        while(child<size){
            //1.找到左右孩子中較小的孩子
            if(child+1<size&&array[child+1]<array[child]){
                child+=1;
            }

            //2.較小的孩子已經(jīng)找到了
            //檢測雙親和孩子之間是否滿足堆的特性
            if(array[parent]>array[child]){
                swap(parent,child);

                //大的雙親往下走，可能會導(dǎo)致子樹又不滿足堆的特性
                //因此需要繼續(xù)往下調(diào)整
                parent=child;
                child=parent*2+1;
            }else{
                //以parent為根的二叉樹已經(jīng)是堆了
                return;
            }
        }
    }

注意： 在調(diào)整以parent為根的二叉樹時，必須要滿足parent的左子樹和右子樹已經(jīng)是堆了才可以向下調(diào)整。
時間復(fù)雜度（看最壞的情況）： 從根一路比較到葉子，比較的次數(shù)為完全二叉樹的高度，即時間復(fù)雜度為O(logn)。

2.堆的創(chuàng)建

向下調(diào)整的情況只能針對左右子樹已經(jīng)是堆了才可以調(diào)整，那假如根結(jié)點的左右子樹不滿足堆的特性，又該如何調(diào)整呢？例如下圖：

我們要從3這里的位置開始向下調(diào)整，然后逐漸向前依次向上調(diào)整
3這個位置很特殊，他是二叉樹倒數(shù)第一個非葉子結(jié)點
步驟：

1.找到倒數(shù)第一個非葉子結(jié)點
2.從該結(jié)點位置開始往前一直到根結(jié)點，每遇到一個結(jié)點就使用向下調(diào)整

代碼實現(xiàn)：

public static void createHeap(int[] array){
    //注意：倒數(shù)第一個非葉子節(jié)點剛好是最后一個節(jié)點的雙親
    //最后一個結(jié)點的編號是size-1，倒數(shù)第一個非葉子節(jié)點的下標(biāo)為（size-1-1）/2
    int lastLeafParent=(size-2)/2;
    //從倒數(shù)第一個非葉子節(jié)點位置開始，一直到根節(jié)點的位置，使用向下調(diào)整
    for(int root=lastLeafParent;root>=0;root--){
       shiftDown(root);
    }
}

建堆的時間復(fù)雜度：
因為堆是完全二叉樹，滿二叉樹也是完全二叉樹，為了簡化計算，此處使用滿二叉樹來證明：
假設(shè)滿二叉樹高度h

第一層：20個結(jié)點，需要向下移動h-1層
第二層：21個結(jié)點，需要向下移動h-2層
第二層：22個結(jié)點，需要向下移動h-3層
…以此類推就可以求出所有的移動步數(shù)：每一層結(jié)點數(shù)與對應(yīng)移動層數(shù)相乘再整體相加
然后再利用一定的數(shù)學(xué)巧妙運算（此處省略那些繁瑣的數(shù)學(xué)公式，屬實是頭大）就得出T(n)=n=log(n+1)≈n

因此：建堆的時間復(fù)雜度為O(N)。

三、向上調(diào)整

向上調(diào)整主要的應(yīng)用場景就是在堆的插入
堆的插入總共需要兩個步驟：

1.先將元素插入到堆的末尾，即最后一個孩子之后
2.插入后如果堆的性質(zhì)遭到破壞，將最后新插入的節(jié)點向上調(diào)整，直到滿足堆的性質(zhì)

代碼實現(xiàn)：

    private void shiftUp(int child){
        int parent=(child-1)/2;

        while(child!=0){
            if(array[child]<array[parent]){
                swap(child,parent);
                child=parent;
                parent=(child-1)/2;
            }else{
                return;
            }
        }
    }

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)中堆的向下和向上調(diào)整解析的文章就介紹到這了,更多相關(guān)Java 數(shù)據(jù)結(jié)構(gòu) 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論