精通八大排序算法系列：二、堆排序算法

     此精通排序算法系列，前一節(jié)，已講過(guò)了一、快速排序算法，其中，快速排序每一趟比較用時(shí)O（n），要進(jìn)行l(wèi)gn次比較，才最終完成整個(gè)排序。所以快排的復(fù)雜度才為O（n*lgn）。而本節(jié)，我們要講的是堆排序算法。據(jù)我所知，要真正徹底認(rèn)識(shí)一個(gè)算法，最好是去查找此算法的原發(fā)明者的論文或相關(guān)文獻(xiàn)。

ok，此節(jié)，咱們開始吧。

一、堆排序算法的基本特性
時(shí)間復(fù)雜度：O(nlgn)...
//等同于歸并排序
最壞：O(nlgn)
空間復(fù)雜度：O(1).
不穩(wěn)定。

二、堆與最大堆的建立
要介紹堆排序算法，咱們得先從介紹堆開始，然后到建立最大堆，最后才講到堆排序算法。

2.1、堆的介紹
    如下圖，

a），就是一個(gè)堆，它可以被視為一棵完全二叉樹。
每個(gè)堆對(duì)應(yīng)于一個(gè)數(shù)組b），假設(shè)一個(gè)堆的數(shù)組A，
我們用length[A]表述數(shù)組中的元素個(gè)數(shù)，heap-size[A]表示本身存放在A中的堆的元素個(gè)數(shù)。
當(dāng)然，就有，heap-size[A]<=length[A]。

    樹的根為A[1]，i表示某一結(jié)點(diǎn)的下標(biāo)，
則父結(jié)點(diǎn)為PARENT(i)，左兒子LEFT[i]，右兒子RIGHT[i]的關(guān)系如下：

PARENT(i)
   return |_i/2_|

LEFT(i)
   return 2i

RIGHT(i)
   return 2i + 1

    二叉堆根據(jù)根結(jié)點(diǎn)與其子結(jié)點(diǎn)的大小比較關(guān)系，分為最大堆和最小堆。
最大堆：
根以外的每個(gè)結(jié)點(diǎn)i都不大于其根結(jié)點(diǎn)，即根為最大元素，在頂端，有
     A[PARENT(i)] （根）≥ A[i] ,

最小堆：
根以外的每個(gè)結(jié)點(diǎn)i都不小于其根結(jié)點(diǎn)，即根為最小元素，在頂端，有
     A[PARENT(i)] （根）≤ A[i] .

在本節(jié)的堆排序算法中，我們采用的是最大堆；最小堆，通常在構(gòu)造最小優(yōu)先隊(duì)列時(shí)使用。

    由前面，可知，堆可以看成一棵樹，所以，堆的高度，即為樹的高度，O(lgn)。
所以，一般的操作，運(yùn)行時(shí)間都是為O(lgn)。

具體，如下：
The MAX-HEAPIFY：O(lgn)  這是保持最大堆的關(guān)鍵.
The BUILD-MAX-HEAP:線性時(shí)間。在無(wú)序輸入數(shù)組基礎(chǔ)上構(gòu)造最大堆。
The HEAPSORT：O(nlgn) time, 堆排序算法是對(duì)一個(gè)數(shù)組原地進(jìn)行排序.
The MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY, HEAP-MAXIMUM：O(lgn)。
可以讓堆作為最小優(yōu)先隊(duì)列使用。 

2.2.1、保持堆的性質(zhì)(O（lgn）)

     為了保持最大堆的性質(zhì)，我們運(yùn)用MAX-HEAPIFY操作，作調(diào)整，遞歸調(diào)用此操作，使i為根的子樹成為最大堆。

MAX-HEAPIFY算法，如下所示（核心）：

MAX-HEAPIFY(A, i)
 1 l ← LEFT(i)
 2 r ← RIGHT(i)
 3 if l ≤ heap-size[A] and A[l] > A[i]
 4    then largest ← l
 5    else largest ← i
 6 if r ≤ heap-size[A] and A[r] > A[largest]
 7    then largest ← r
 8 if largest ≠ i
 9    then exchange A[i] <-> A[largest]
10         MAX-HEAPIFY(A, largest) 

     如上，首先第一步，在對(duì)應(yīng)的數(shù)組元素A[i], 左孩子A[LEFT(i)], 和右孩子A[RIGHT(i)]中找到最大的那一個(gè)，將其下標(biāo)存儲(chǔ)在largest中。如果A[i]已經(jīng)就是最大的元素，則程序直接結(jié)束。否則，i的某個(gè)子結(jié)點(diǎn)為最大的元素，將其，即A[largest]與A[i]交換，從而使i及其子女都能滿足最大堆性質(zhì)。下標(biāo)largest所指的元素變成了A[i]的值，會(huì)違反最大堆性質(zhì)，所以對(duì)largest所指元素調(diào)用MAX-HEAPIFY。如下，是此MAX-HEAPIFY的演示過(guò)程（下圖是把4調(diào)整到最底層，一趟操作，但摸索的時(shí)間為L(zhǎng)ogN）：

     由上圖，我們很容易看出，初始構(gòu)造出一最大堆之后，在元素A[i]，即16，大于它的倆個(gè)子結(jié)點(diǎn)4、10，滿足最大堆性質(zhì)。所以，i下調(diào)指向著4,小于,左子14，所以，調(diào)用MAX-HEAPIFY，4與其子，14交換位置。但4處在了14原來(lái)的位置之后，4小于其右子8，又違反了最大堆的性質(zhì)，所以再遞歸調(diào)用MAX-HEAPIFY，將4與8，交換位置。于是，滿足了最大堆性質(zhì)，程序結(jié)束。

2.2.2、MAX-HEAPIFY的運(yùn)行時(shí)間
   MAX-HEAPIFY作用在一棵以結(jié)點(diǎn)i為根的、大小為n的子樹上時(shí)，其運(yùn)行時(shí)間為調(diào)整元素A[i]、A[LEFT(i)]，A[RIGHT(i)]的關(guān)系時(shí)所用時(shí)間為O(1)，再加上，對(duì)以i的某個(gè)子結(jié)點(diǎn)為根的子樹調(diào)用MAX-HEAPIFY所需的時(shí)間，且i結(jié)點(diǎn)的子樹大小至多為2n/3，所以，MAX-HEAPIFY的運(yùn)行時(shí)間為
     T (n) ≤ T(2n/3) + Θ(1).

我們，可以證得此式子的遞歸解為T(n)=O(lgn)。具體證法，可參考算法導(dǎo)論第6章之6.2節(jié)，這里，略過(guò)。

2.3.1、建堆(O（N）)

BUILD-MAX-HEAP(A)
1  heap-size[A] ← length[A]
2  for i ← |_length[A]/2_| downto 1
3       do MAX-HEAPIFY(A, i)    //建堆，怎么建列?原來(lái)就是不斷的調(diào)用MAX-HEAPIFY(A, i)來(lái)建立最大堆。

BUILD-MAX-HEAP通過(guò)對(duì)每一個(gè)其它結(jié)點(diǎn)，都調(diào)用一次MAX-HEAPIFY，
來(lái)建立一個(gè)與數(shù)組A[1...n]相對(duì)應(yīng)的最大堆。A[(|_n/2_|+1) ‥ n]中的元素都是樹中的葉子。
因此，自然而然，每個(gè)結(jié)點(diǎn)，都可以看作一個(gè)只含一個(gè)元素的堆。

關(guān)于此過(guò)程BUILD-MAX-HEAP(A)的正確性，可參考算法導(dǎo)論 第6章之6.3節(jié)。
下圖，是一個(gè)此過(guò)程的例子（下圖是不斷的調(diào)用MAX-HEAPIFY操作，把所有的違反堆性質(zhì)的數(shù)都要調(diào)整，共N趟操作，然，摸索時(shí)間最終精確為O（N））：

2.3.2、BUILD-MAX-HEAP的運(yùn)行時(shí)間
       因?yàn)槊看握{(diào)用MAX-HEAPPIFY的時(shí)間為O(lgn)，而共有O(n)次調(diào)用，所以BUILD-MAX-HEAP的簡(jiǎn)單上界為O(nlgn)。算法導(dǎo)論一書提到，盡管這個(gè)時(shí)間界是對(duì)的，但從漸進(jìn)意義上，還不夠精確。

       那么，更精確的時(shí)間界，是多少列?
由于，MAX-HEAPIFY在樹中不同高度的結(jié)點(diǎn)處運(yùn)行的時(shí)間不同，且大部分結(jié)點(diǎn)的高度都比較小，
而我們知道，一n個(gè)元素的堆的高度為|_lgn_|(向下取整)，且在任意高度h上，至多有|-n/2^h+1-|(向上取整)個(gè)結(jié)點(diǎn)。

因此，MAX-HEAPIFY作用在高度為h的結(jié)點(diǎn)上的時(shí)間為O(h)，所以，BUILD-MAX-HEAP的上界為：O（n）。具體推導(dǎo)過(guò)程，略。
 

三、堆排序算法

     所謂的堆排序，就是調(diào)用上述倆個(gè)過(guò)程：一個(gè)建堆的操作、BUILD-MAX-HEAP，一個(gè)保持最大堆的操作、MAX-HEAPIFY。詳細(xì)算法如下：

HEAPSORT(A)    //n-1次調(diào)用MAX-HEAPIFY，所以，O（n*lgn）
1 BUILD-MAX-HEAP(A)      //建最大堆，O（n）
2 for i ← length[A] downto 2
3    do exchange A[1] <-> A[i]
4       heap-size[A] ← heap-size[A] - 1
5       MAX-HEAPIFY(A, 1)    //保持堆的性質(zhì)，O（lgn） 

     如上，即是堆排序算法的完整表述。下面，再貼一下上述堆排序算法中的倆個(gè)建堆、與保持最大堆操作：
BUILD-MAX-HEAP(A)  //建堆
1  heap-size[A] ← length[A]
2  for i ← |_length[A]/2_| downto 1
3       do MAX-HEAPIFY(A, i)

MAX-HEAPIFY(A, i)     //保持最大堆
 1 l ← LEFT(i)
 2 r ← RIGHT(i)
 3 if l ≤ heap-size[A] and A[l] > A[i]
 4    then largest ← l
 5    else largest ← i
 6 if r ≤ heap-size[A] and A[r] > A[largest]
 7    then largest ← r
 8 if largest ≠ i
 9    then exchange A[i] <-> A[largest]
10         MAX-HEAPIFY(A, largest) 

以下是，堆排序算法的演示過(guò)程（通過(guò)，頂端最大的元素與最后一個(gè)元素不斷的交換，交換后又不斷的調(diào)用MAX-HEAPIFY以重新維持最大堆的性質(zhì)，最后，一個(gè)一個(gè)的，從大到小的，把堆中的所有元素都清理掉，也就形成了一個(gè)有序的序列。這就是堆排序的全部過(guò)程。）：

上圖中，a->b，b->c，....之間，都有一個(gè)頂端最大元素與最小元素交換后，調(diào)用MAX-HEAPIFY的過(guò)程，我們知道，此MAX-HEAPIFY的運(yùn)行時(shí)間為O（lgn），而要完成整個(gè)堆排序的過(guò)程，共要經(jīng)過(guò)O（n）次這樣的MAX-HEAPIFY操作。所以，才有堆排序算法的運(yùn)行時(shí)間為O（n*lgn）。

后續(xù)：把堆想象成為一種樹，二叉樹之類的。所以，用堆做數(shù)據(jù)查找、刪除的時(shí)間復(fù)雜度皆為O（logN）。那么是一種什么樣的二叉樹列?一種特殊的二叉樹，分為最大堆，最小堆。最大堆，就是上頭大，下頭小。最小堆就是上頭小，下頭大。

完。