MIT公開課沒有講到的內(nèi)容，堆排序
主要部分內(nèi)容引用自Blog：https://www.cnblogs.com/Anker/archive/2013/01/23/2873422.html
和《算法導(dǎo)論》

- 介紹堆，最大堆，最小堆
- 構(gòu)建最大堆
- 堆排序算法
- 優(yōu)先級(jí)隊(duì)列

什么是堆
堆給人的感覺是一個(gè)二叉樹，但是其本質(zhì)是一種數(shù)組對(duì)象，因?yàn)閷?duì)堆進(jìn)行操作的時(shí)候?qū)⒍岩暈橐活w完全二叉樹，樹種每個(gè)節(jié)點(diǎn)與數(shù)組中的存放該節(jié)點(diǎn)值的那個(gè)元素對(duì)應(yīng)。所以堆又稱為二叉堆，堆與完全二叉樹的對(duì)應(yīng)關(guān)系如下圖所示

通常給定節(jié)點(diǎn)i，可以根據(jù)其在數(shù)組中的位置求出該節(jié)點(diǎn)的父親節(jié)點(diǎn)、左右孩子節(jié)點(diǎn)，這三個(gè)過程一般采用宏或者內(nèi)聯(lián)函數(shù)實(shí)現(xiàn)。數(shù)組的下標(biāo)是從1開始的，可以得到：
parent(i)=i/2　　left(i) = 2*i 　　right(i) = 2*i+1

最大堆和最小堆
根據(jù)節(jié)點(diǎn)數(shù)值滿足的條件，可以將分為最大堆和最小堆
最大堆的特性是：除了根節(jié)點(diǎn)以外的每個(gè)節(jié)點(diǎn)i，有A[parent(i)] >= A[i]
最小堆的特性是：除了根節(jié)點(diǎn)以外的每個(gè)節(jié)點(diǎn)i，有A[parent(i)] >=A[i]

如果把堆看成一個(gè)棵樹，有如下的特性：

1. 含有n個(gè)元素的堆的高度是lgn
2. 當(dāng)用數(shù)組表示存儲(chǔ)了n個(gè)元素的堆時(shí)，葉子節(jié)點(diǎn)的下標(biāo)是n/2+1，n/2+2，……，n
3. 在最大堆中，最大元素該子樹的根上；在最小堆中，最小元素在該子樹的根上

堆有個(gè)關(guān)鍵操作過程是如何保持堆的特有性質(zhì)，給定一個(gè)節(jié)點(diǎn)i，子樹滿足堆性要保證以i為根的質(zhì)。以最大堆作為例子介紹，并給出了遞歸形式的保持最大堆特性的操作過程MAX-HEAPIFY

MAX-HEAPIFY(A, i)
l <- left(i)
r <- right(i)
if l <= heap-size(A) and A[l] > A[i]
    then largest <- l
    else largest <- i
if r <= heap-size(A) and A[r] > A[largest]
    then largest <- r
if largest not equal r
    then exch A[i] <-> A[largest]
        MAX-HEAPIFY(A, largest)

輸入為數(shù)組A和下標(biāo)i，結(jié)果使以i為根的子樹稱為最大堆，假定left(i)和right(i)為根的兩個(gè)子樹都是最大堆，如果A[i]小于其子女，讓A[i]在最大堆中“下降”

操作過程如下圖所示：
在節(jié)點(diǎn)i=2時(shí)，不滿足最大堆的要求，需要進(jìn)行調(diào)整，選擇節(jié)點(diǎn)2的左右孩子中最大一個(gè)進(jìn)行交換，然后檢查交換后的節(jié)點(diǎn)i=4是否滿足最大堆的要求，從圖看出不滿足，接著進(jìn)行調(diào)整，直到?jīng)]有交換為止。

堆操作

擴(kuò)展
課后習(xí)題要求給出其非遞歸的形式，非遞歸就要考慮要循環(huán)進(jìn)行實(shí)現(xiàn)，需要考慮的是循環(huán)結(jié)束條件是什么。對(duì)一個(gè)給定的節(jié)點(diǎn)i，要對(duì)其進(jìn)行調(diào)整使其滿足最大堆的性質(zhì)?？偟乃枷胧窍日页龉?jié)點(diǎn)i的左右孩子節(jié)點(diǎn)，然后從三者中找到最大的節(jié)點(diǎn)，如果找到的最大節(jié)點(diǎn)就是i，說(shuō)明i節(jié)點(diǎn)滿足堆的性質(zhì)，此時(shí)循環(huán)就結(jié)束了。如果找到的最大節(jié)點(diǎn)不是節(jié)點(diǎn)i，那么這個(gè)時(shí)候就要將最大的節(jié)點(diǎn)（設(shè)為largest）與節(jié)點(diǎn)i進(jìn)行交換，然后從largest節(jié)點(diǎn)開始循環(huán)進(jìn)行調(diào)整，直到滿足條件為止。

MAX-HEAP(A, i)
while true
    l <- left(i)
    r <- right(i)
    if l <= heap-size(A) and A[l] > A[i]
        then largest = l
        else largest = i
    if r <= heap-size(A) and A[r] > A[largest]
        largest <- r
    if largest not equal i
        then exch A[i] <-> A[largest]
            continue;
        else break;

建堆

建立最大堆的過程是自底向上地調(diào)用最大堆調(diào)整程序?qū)⒁粋€(gè)數(shù)組A[1.....N]變成一個(gè)最大堆。將數(shù)組視為一顆完全二叉樹，從其最后一個(gè)非葉子節(jié)點(diǎn)（n/2）開始調(diào)整。調(diào)整過程如下圖所示：

建堆過程

偽代碼

BUILD-MAX-HEAP(A)
heap-size(A) <- length(A)
for i <- length(A)/2 down to 1
      do MAX-HEAPIFY(A, i)

堆排序算法
堆排序算法過程為：先調(diào)用創(chuàng)建堆函數(shù)將輸入數(shù)組A[1...n]造成一個(gè)最大堆，使得最大的值存放在數(shù)組第一個(gè)位置A[1]，然后用數(shù)組最后一個(gè)位置元素與第一個(gè)位置進(jìn)行交換，并將堆的大小減少1，并調(diào)用最大堆調(diào)整函數(shù)從第一個(gè)位置調(diào)整最大堆。給出堆數(shù)組A={4,1,3,16,9,10,14,8,7}進(jìn)行堆排序簡(jiǎn)單的過程如下：

1. 創(chuàng)建最大堆，數(shù)組第一個(gè)元素最大，執(zhí)行后結(jié)果下圖：

   
   

2. 進(jìn)行循環(huán)，從length(a)到2，并不斷的調(diào)整最大堆，給出一個(gè)簡(jiǎn)單過程如下：

   
   

HEAP-SORT(A)
BUILD-MAX-HEAP(A)
for i <- length(A) down to 2
    do exch A[1] <-> A[i]
        heap-size(A) <- heap-size(A) - 1
        MAX-HEAPIFY(A, 1)

堆排序算法時(shí)間復(fù)雜度：調(diào)整堆過程滿足遞歸式T(n)<=T(2n/3)+θ(1)，有主定理可以知道T(n) = O(lgn)，堆排序過程中執(zhí)行一個(gè)循環(huán)，調(diào)用最大堆調(diào)整函數(shù)，總的時(shí)間復(fù)雜度為O(nlgn）

思考
在創(chuàng)建最大堆的過程中，為什么從最后一個(gè)非葉子節(jié)點(diǎn)（n/2）開始到第一個(gè)非葉子（1）結(jié)束，而不是從第一個(gè)非葉子節(jié)點(diǎn)（1）到最后一個(gè)非葉子節(jié)點(diǎn)（n/2）結(jié)束呢？
作者的想法是：如果是從第一個(gè)非葉子節(jié)點(diǎn)開始創(chuàng)建堆，有可能導(dǎo)致創(chuàng)建的堆不滿足堆的性質(zhì)，使得第一個(gè)元素不是最大的。這樣做只是使得該節(jié)點(diǎn)的和其左右孩子節(jié)點(diǎn)滿足堆性質(zhì)，不能確保整個(gè)樹滿足堆的性質(zhì)。如果最大的節(jié)點(diǎn)在葉子節(jié)點(diǎn)，那么將可能不會(huì)出現(xiàn)在根節(jié)點(diǎn)中。例如下面的例子：

從圖中可以看出，從第一個(gè)非葉子節(jié)點(diǎn)開始創(chuàng)建最大堆，最后得到的結(jié)果并不是最大堆。而從最后一個(gè)非葉子節(jié)點(diǎn)開始創(chuàng)建堆時(shí)候，能夠保證該節(jié)點(diǎn)的子樹都滿足堆的性質(zhì)，從而自底向上進(jìn)行調(diào)整堆，最終使得滿足最大堆的性質(zhì)。

優(yōu)先級(jí)隊(duì)列
快速排序往往優(yōu)于堆排序，但是堆排序有一個(gè)常見應(yīng)用：優(yōu)先級(jí)隊(duì)列
最大優(yōu)先級(jí)隊(duì)列和最小優(yōu)先級(jí)隊(duì)列對(duì)應(yīng)最大堆和最小堆
優(yōu)先級(jí)隊(duì)列一般操作
-在隊(duì)列中插入數(shù)據(jù)
-返回隊(duì)列中的最大或最小值
-從隊(duì)列中移除數(shù)據(jù)
-增加或減小關(guān)鍵字的值