有沒有發(fā)現(xiàn)這棵二叉樹有一個特點(diǎn)，就是所有父結(jié)點(diǎn)都比子結(jié)點(diǎn)要?。ㄗ⒁猓簣A圈里面的數(shù)是值，圓圈上面的數(shù)是這個結(jié)點(diǎn)的編號，此規(guī)定僅適用于本節(jié)）。符合這樣特點(diǎn)的完全二叉樹我們稱為最小堆。反之，如果所有父結(jié)點(diǎn)都比子結(jié)點(diǎn)要大，這樣的完全二叉樹稱為最大堆。那這一特性究竟有什么用呢？

假如有 14 個數(shù)分別是 99、5、36、7、22、17、46、12、2、19、25、28、1 和 92。請找出這 14 個數(shù)中最小的數(shù)，請問怎么辦呢？最簡單的方法就是將這 14 個數(shù)從頭到尾依次掃一遍，用一個循環(huán)就可以解決。這種方法的時間復(fù)雜度是 O(14)也就是 O(N)。


    for(i=1;i<=14;i++)
    {
        if(a[ i]<min)min=a[ i];
    }

現(xiàn)在我們需要刪除其中最小的數(shù)，并增加一個新數(shù) 23，再次求這 14 個數(shù)中最小的一個數(shù)。請問該怎么辦呢？只能重新掃描所有的數(shù)，才能找到新的最小的數(shù)，這個時間復(fù)雜度也是 O(N)。假如現(xiàn)在有 14 次這樣的操作（刪除最小的數(shù)后并添加一個新數(shù)）。那么整個時間復(fù)雜度就是 O(142)即 O(N2)。那有沒有更好的方法呢？堆這個特殊的結(jié)構(gòu)恰好能夠很好地解決這個問題。

首先我們先把這個 14 個數(shù)按照最小堆的要求（就是所有父結(jié)點(diǎn)都比子結(jié)點(diǎn)要?。┓湃胍豢猛耆鏄?，就像下面這棵樹一樣。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/11.2.png" alt="picture11.2" />

很顯然最小的數(shù)就在堆頂，假設(shè)存儲這個堆的數(shù)組叫做h的話，最小數(shù)就是 h[ 1]。接下來，我們將堆頂?shù)臄?shù)刪除，并將新增加的數(shù) 23 放到堆頂。顯然加了新數(shù)后已經(jīng)不符合最小堆的特性，我們需要將新增加的數(shù)調(diào)整到合適的位置。那如何調(diào)整呢？

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/11.3.png" alt="picture11.3" />

向下調(diào)整！我們需要將這個數(shù)與它的兩個兒子 2 和 5 比較，并選擇較小一個與它交換，交換之后如下。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/11.4.png" alt="picture11.4" />

我們發(fā)現(xiàn)此時還是不符合最小堆的特性，因此還需要繼續(xù)向下調(diào)整。于是繼續(xù)將 23 與它的兩個兒子 12 和7比較，并選擇較小一個交換，交換之后如下。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/11.5.png" alt="picture11.5" />

到此，還是不符合最小堆的特性，仍需要繼續(xù)向下調(diào)整直到符合最小堆的特性為止。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/11.6.png" alt="picture11.6" />

我們發(fā)現(xiàn)現(xiàn)在已經(jīng)符合最小堆的特性了。綜上所述，當(dāng)新增加一個數(shù)被放置到堆頂時，如果此時不符合最小堆的特性，則將需要將這個數(shù)向下調(diào)整，直到找到合適的位置為止，使其重新符合最小堆的特性。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/11.7.png" alt="picture11.7" />

向下調(diào)整的代碼如下。


    void siftdown(int i) //傳入一個需要向下調(diào)整的結(jié)點(diǎn)編號i，這里傳入1，即從堆的頂點(diǎn)開始向下調(diào)整 
    {
        int t,flag=0;//flag用來標(biāo)記是否需要繼續(xù)向下調(diào)整 
        //當(dāng)i結(jié)點(diǎn)有兒子的時候（其實是至少有左兒子的情況下）并且有需要繼續(xù)調(diào)整的時候循環(huán)窒執(zhí)行
        while( i*2<=n && flag==0 )
        {        
            //首先判斷他和他左兒子的關(guān)系，并用t記錄值較小的結(jié)點(diǎn)編號 
            if( h[ i] > h[ i*2] )
                t=i*2;
            else
                t=i; 
            //如果他有右兒子的情況下，再對右兒子進(jìn)行討論 
            if(i*2+1 <= n)
            {
                //如果右兒子的值更小，更新較小的結(jié)點(diǎn)編號  
                if(h[ t] > h[ i*2+1])
                    t=i*2+1;
            }
            //如果發(fā)現(xiàn)最小的結(jié)點(diǎn)編號不是自己，說明子結(jié)點(diǎn)中有比父結(jié)點(diǎn)更小的  
            if(t!=i)
            {
                swap(t,i);//交換它們，注意swap函數(shù)需要自己來寫
                i=t;//更新i為剛才與它交換的兒子結(jié)點(diǎn)的編號，便于接下來繼續(xù)向下調(diào)整 
            }
            else
                flag=1;//則否說明當(dāng)前的父結(jié)點(diǎn)已經(jīng)比兩個子結(jié)點(diǎn)都要小了，不需要在進(jìn)行調(diào)整了 
        }
    }

我們剛才在對 23 進(jìn)行調(diào)整的時候，竟然只進(jìn)行了 3 次比較，就重新恢復(fù)了最小堆的特性?，F(xiàn)在最小的數(shù)依然在堆頂為 2。之前那種從頭到尾掃描的方法需要 14 次比較，現(xiàn)在只需要 3 次就夠了。現(xiàn)在每次刪除最小的數(shù)并新增一個數(shù)，并求當(dāng)前最小數(shù)的時間復(fù)雜度是 O(3)，這恰好是 O(log214)即 O(log2N)簡寫為 O(logN)。假如現(xiàn)在有 1 億個數(shù)（即 N=1 億），進(jìn)行 1 億次刪除最小數(shù)并新增一個數(shù)的操作，使用原來掃描的方法計算機(jī)需要運(yùn)行大約 1 億的平方次，而現(xiàn)在只需要 1 億*log1 億次，即 27 億次。假設(shè)計算機(jī)每秒鐘可以運(yùn)行 10 億次，那原來則需要一千萬秒大約 115 天！而現(xiàn)在只要 2.7 秒。是不是很神奇，再次感受到算法的偉大了吧。

說到這里，如果只是想新增一個值，而不是刪除最小值又該如何操作呢？即如何在原有的堆上直接插入一個新元素呢？只需要直接將新元素插入到末尾，再根據(jù)情況判斷新元素是否需要上移，直到滿足堆的特性為止。如果堆的大小為 N（即有 N 個元素），那么插入一個新元素所需要的時間也是 O(logN)。例如我們現(xiàn)在要新增一個數(shù) 3。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/11.8.png" alt="picture11.8" />

先將 3 與它的父結(jié)點(diǎn) 25 比較，發(fā)現(xiàn)比父結(jié)點(diǎn)小，為了維護(hù)最小堆的特性，需要與父結(jié)點(diǎn)的值進(jìn)行交換。交換之后發(fā)現(xiàn)還是要比它此時的父結(jié)點(diǎn) 5 小，因此需要再次與父結(jié)點(diǎn)交換。至此又重新滿足了最小堆的特性。向上調(diào)整完畢后如下。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/11.9.png" alt="picture11.9" />

向上調(diào)整的代碼如下。


    void siftup(int i) //傳入一個需要向上調(diào)整的結(jié)點(diǎn)編號i
    {
        int flag=0; //用來標(biāo)記是否需要繼續(xù)向上調(diào)整
        if(i==1)  return; //如果是堆頂，就返回，不需要調(diào)整了    
        //不在堆頂 并且 當(dāng)前結(jié)點(diǎn)i的值比父結(jié)點(diǎn)小的時候繼續(xù)向上調(diào)整 
        while(i!=1 && flag==0)
        {
            //判斷是否比父結(jié)點(diǎn)的小 
            if(h[ i]<h[ i/2])
                swap(i,i/2);//交換他和他爸爸的位置 
            else
                flag=1;//表示已經(jīng)不需要調(diào)整了，當(dāng)前結(jié)點(diǎn)的值比父結(jié)點(diǎn)的值要大 
            i=i/2; //這句話很重要，更新編號i為它父結(jié)點(diǎn)的編號，從而便于下一次繼續(xù)向上調(diào)整 
        }
    }

上一篇：算法 4：隊列——解密 QQ 號下一篇：算法 2：鄰居好說話：冒泡排序