前言

上一篇寫了數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹、AVL自平衡樹，這次來寫堆。

堆的創(chuàng)造者

很久以前排序算法的時(shí)間復(fù)雜度一直是O(n^2)， 當(dāng)時(shí)學(xué)術(shù)界充斥著“排序算法不可能突破O(n^2)”的聲音，直到1959年，由D.L.Shell提出了一種排序算法，希爾排序（Shell Sort），才打破了這種不可能的聲音，把排序算法的時(shí)間復(fù)雜度提升到了O(n^3/2)！

當(dāng)科學(xué)家們知道這種"不可能"被突破之后，又相繼有了更快的排序算法，“不可能超越O（n^2）”徹底成為了歷史。

在1964年，沒錯(cuò)，是55年前！堆排序這種奇思妙想的，十分精彩的，排序算法誕生了！時(shí)間復(fù)雜度為O(nlogn)，遠(yuǎn)甩O（n^2）

由Robert W. Floyd（羅伯特·弗洛伊德）和J.W.J. Williams（威廉姆斯）共同發(fā)明了著名的堆排序，同時(shí)也發(fā)明了“堆”這樣的數(shù)據(jù)結(jié)構(gòu)， Floyd在1978年獲得了圖靈獎(jiǎng)！真是個(gè)狼人?。。ū群苋诉€要多一點(diǎn)）

有時(shí)候了解下歷史，也是十分有趣的！雖然你可能會(huì)覺得并沒什么卵用~

堆是什么？

之前第一次聽到堆這個(gè)詞的時(shí)候，感覺像是一堆亂七八糟的東西，完全跟樹連想不到一起，后來才知道，原來堆也是一顆二叉樹，而且是完全二叉樹

堆的性質(zhì)：

堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
堆總是一棵完全二叉樹。

大頂堆

小頂堆

如何用數(shù)組表示堆？

我們可以把堆，存放在一個(gè)數(shù)組中，根據(jù)索引來獲取節(jié)點(diǎn)，那么如何通過索引表示父子關(guān)系呢？
堆是一顆完全二叉樹，所以滿足如下條件

假如當(dāng)前的節(jié)點(diǎn)索引為：k
父節(jié)點(diǎn)索引：(k-1) / 2
左孩子節(jié)點(diǎn)：2 * k + 1
右孩子節(jié)點(diǎn)：2 * k + 2

根據(jù)這個(gè)規(guī)律，我們就可以用索引來計(jì)算出父子節(jié)點(diǎn)的位置了。這樣就能把堆存放在數(shù)組中使用，會(huì)更加節(jié)省內(nèi)存。

堆排序算法

堆排序算法就是形成一個(gè)堆后，假如是大頂堆，堆頂肯定是最大的元素，那我們每次都把堆頂?shù)淖畲笤啬米?，然后把堆末尾的元素放到堆頂來，但是這個(gè)元素不一定是當(dāng)前最大的，所以還要對(duì)這個(gè)元素在堆里進(jìn)行比較，把最大的元素放到堆頂，再取出來。如此我們每次取出的都是剩余元素中最大的元素，就能得到一組從大到小有序的元素。下面我們來用大頂堆對(duì)一組數(shù)據(jù)進(jìn)行堆排序計(jì)算。

數(shù)據(jù)為：[50, 10, 90, 30, 70, 40, 80, 60, 20]

算法分為兩個(gè)部分

1.如何將一組無序的數(shù)據(jù)構(gòu)建出一個(gè)初始的大頂堆？
2.在拿走堆頂元素之后，如何計(jì)算出新的堆頂元素？

首先我們要實(shí)現(xiàn)一個(gè)操作：如果一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)比它更大，就交換位置，如果子節(jié)點(diǎn)還有子節(jié)點(diǎn)，就要繼續(xù)比下去，直到末尾。這個(gè)操作我們稱為：HeapOne

    public void HeapOne(List<int> list, int len, int s)
    {
        int temp, j;
        
        temp = list[s];//先把指定要下沉節(jié)點(diǎn)的值取出來
        
        for (j = (2 * s)+1; j < len; j = (j*2)+1)
        {
            if (j < (len - 1) && list[j] < list[j + 1])//看看左右兩個(gè)子節(jié)點(diǎn)誰更大，就取誰
                ++j;
            
            if (temp >= list[j])//子節(jié)點(diǎn)比父節(jié)點(diǎn)小，就不管
                break;

            list[s] = list[j];//先把子節(jié)點(diǎn)的值給父節(jié)點(diǎn)
            s = j;//繼續(xù)從這個(gè)子節(jié)點(diǎn)往下比較下去
        }
        list[s] = temp;
    }

實(shí)現(xiàn)這個(gè)操作之后，就可以開始我們的第一個(gè)部分了，形成初始大頂堆。

從最后一個(gè)非葉子節(jié)點(diǎn)開始，對(duì)該節(jié)點(diǎn)進(jìn)行HeapOne，一直從下往上，直到把所有的父節(jié)點(diǎn)都HeapOne了一遍，一個(gè)初始的大頂堆就形成了。

    public void HeapSort(List<int> list)
    {
        int i;
        for (i = (list.Count - 1) / 2; i >= 0; i--)//第一部分，形成一個(gè)初始大頂堆
        {
            HeapOne(list, list.Count, i);
        }

        for (i = list.Count -1; i > 0; i--)//每拿走一個(gè)元素，都重新計(jì)算新堆
        {
            int temp = list[0];
            list[0] = list[i];
            list[i] = temp;
            
            HeapOne(list, i, 0);
        }
    }

算法第二部分

1. 我們把堆頂?shù)脑厝〕?，放到一個(gè)臨時(shí)變量里存著。
2. 然后把堆的最末尾元素取出來，放到堆頂。
3. 把堆的長度-1（因?yàn)橐呀?jīng)取出之前的堆頂元素了）
4. 接著對(duì)剛剛這個(gè)從末尾放到堆頂?shù)脑兀M(jìn)行HeapOne操作，讓他跟子節(jié)點(diǎn)比較，把最大的元素交換到堆頂來，再次形成最大堆。

一直重復(fù)這個(gè)操作后，直到最后一個(gè)堆頂被取出，放到數(shù)組末尾，堆的長度也就為0了，我們的數(shù)組也就形成了一組從大到小的數(shù)列。

如此，堆排序就完成了

總結(jié)

堆排序性能比較穩(wěn)定，時(shí)間復(fù)雜度包含初始堆+排序時(shí)重建堆為：O(nlogn)。
在游戲開發(fā)中也會(huì)經(jīng)常使用到堆

1. 比如Top K問題，從n個(gè)數(shù)據(jù)中，找出最大的前100個(gè)。
2. 用堆來實(shí)現(xiàn)優(yōu)先加載隊(duì)列。
3. A星尋路算法中，可以用最小堆來對(duì)尋路的開放列表維護(hù)順序，把f值最小的放在堆頂，每次取出堆頂后，再HeapOne一次就好了。比每次都對(duì)開放列表進(jìn)行排序的性能高的多。

參考

百度百科-堆排序
《大話數(shù)據(jù)結(jié)構(gòu)》-程杰