上次寫到了快排实辑，接著往下講捺氢。O（nlogn）級別的算法除了上次說的快排，歸并剪撬，還有推排序摄乒。今天從先推排序開始寫。堆排序是堆的一個主要應(yīng)用残黑，要說清楚推排序就要先介紹堆馍佑，而且后面打算寫一下計算時間復雜度（我自己算了一遍感覺挺有意思），所以堆排序可能會寫的長一點梨水。
說明：
1.如果你不清楚樹拭荤，建議先了解一下樹再往下看
2.本文是個人學習筆記，參考了算法導論和網(wǎng)上其他文章
一疫诽、二叉堆
1.定義
二叉堆是棵完全二叉樹（后面會用到一些完全二叉樹的性質(zhì)）舅世，并且父結(jié)點的鍵值總是大于等于（叫最大堆）或小于等于（最小堆）子節(jié)點的鍵值旦委。并且每個結(jié)點的左子樹和右子樹都是一個二叉堆（都是最大堆或最小堆）。
因為二叉堆最常用雏亚，一般簡稱的堆就是指二叉堆缨硝。
2.表示
一般是用數(shù)組表示，因為堆是完全二叉樹罢低，用數(shù)組儲存不會浪費空間查辩。上面這個堆可以表示為：
左右孩子下標分別為2 * i + 1和2 * i + 2。
用Java寫一個堆應(yīng)該先聲明堆類网持，定義各種成員變量和方法宜岛，寫構(gòu)造函數(shù)等等，由于我們這里主要為了寫堆排序算法功舀，所以下面就只介紹三個重要操作插入萍倡、刪除、建堆辟汰，然后寫三個函數(shù)遣铝。圖解如下。
3.插入節(jié)點
假設(shè)現(xiàn)在已經(jīng)有了一個堆莉擒，插入一個新節(jié)點，步驟如下：
- 堆的大小+1
- 新節(jié)點放在堆的尾部（數(shù)組最后一個位置）
- 從下至上（根）調(diào)整新節(jié)點位置瘫絮，令其再次滿足堆的定義（這個步驟叫堆化）
可以發(fā)現(xiàn)從這個新結(jié)點到它的父節(jié)點一直向上涨冀，到根結(jié)點必然為一個有序的數(shù)列，現(xiàn)在的任務(wù)是將這個新數(shù)據(jù)插入到這個有序數(shù)列的合適中麦萤。是不是和之前寫的插入排序很像鹿鳖？其實代碼寫法也差不多，只是現(xiàn)在不需要依次往前遍歷數(shù)組壮莹，只要一層一層往上遍歷翅帜，所以一次插入的時間復雜度也從O（n）變得更快了。代碼如下：
void insert(int[] A, int count, int data){
int i,temp;
i=count++;
A[i]=data;
while(i!=0&&(i-1)/2>=0&&A[(i-1)/2]<data){
temp=A[i];
A[i]=A[(i-1)/2];
A[(i-1)/2]=temp;
i=(i-1)/2
}
}
時間復雜度為O（logn）命满，因為在最壞情況下涝滴，需要從最后一層出發(fā)，一直向上到根節(jié)點胶台，遍歷的次數(shù)就是樹的高度歼疮。那么為什么樹的高度h=logn？
這是因為堆是個完全二叉樹诈唬。除了最底層韩脏，其他層都是滿的，故它的節(jié)點個數(shù)n為2h~2(h+1)-1铸磅，h表示樹高赡矢。這就表明h<=logn<=h+1杭朱，由于h為整數(shù)，所以h=logn吹散。
4.刪除節(jié)點
堆只能刪除根節(jié)點（最大或最小節(jié)點）弧械。操作如下：
- 根節(jié)點與最后一個節(jié)點交換并刪除它（就是直接把最后一個節(jié)點賦值給根節(jié)點）
- 從根節(jié)點開始向下堆化，令其再次滿足堆的定義送浊。
向下堆化和上面的向上堆化差不多梦谜，但是是和子節(jié)點中最大（最小）的比較袭景，交換唁桩。調(diào)整時先在左右兒子結(jié)點中找最大的，如果父結(jié)點比這個最大的子結(jié)點還大說明不需要調(diào)整了耸棒，反之將父結(jié)點和它交換后再考慮后面的結(jié)點荒澡。這個過程也叫"向下滲透"。
int delete(int[] A, int count){
if(count==-1)
return -1;//當堆為空時与殃，報錯
int data = A[0];
A[0]=A[count--];
down(int[] A, int count);
return data;//返回刪除的值
}
//向下堆化
void down(int[] A,int count){
int i =0;//從根節(jié)點開始
int r,l;
int maxson;
for(l=2*i+1,r=2*i+2;;){
if(r<=count){
if(A[l]>A[r])
maxson=l;
else
maxson=r;
}
else if(l<=count&&r>count)
maxson=l;
else if(l>count)
break;
if(A[maxson]>A[i]){
int temp=A[i];
A[i]=A[maxson];
A[maxson]=temp;
i=maxson;
}
else
break;
}
}
復雜度同插入单山，原因也一樣
5.建堆
建堆的一個簡單思路是，將輸入數(shù)據(jù)依次插入空堆中幅疼，這需要n次連續(xù)插入操作米奸，最壞情況時間復雜度O（nlogn）。
不過建堆顯然不用這么麻煩爽篷，看下面這種思路悴晰。葉子節(jié)點沒有子節(jié)點，可以視作已經(jīng)是滿足條件的堆逐工。從最后一非葉子節(jié)點開始向下堆化铡溪，直到根節(jié)點。觀察發(fā)現(xiàn)最后一個非葉子節(jié)點就是最后一個節(jié)點的父節(jié)點泪喊。比如下面這個堆棕硫，按紅色序號的順序分別向下堆化。
void build(int[] A,int count){
for(int i=(count-1)/2;i>0;i--){
down(A,count,i);
}
顯然袒啼，這種方法效率更高哈扮。因為只對幾乎一半的節(jié)點進行了堆化。而且下層節(jié)點數(shù)量遠大于上層節(jié)點（下層節(jié)點數(shù)量是倍增的）瘤泪，向下堆化灶泵，下層節(jié)點交換次數(shù)少，向上堆化对途，下層節(jié)點交換次數(shù)多赦邻。計算后這種方法可以在時間O（n）內(nèi)完成。具體計算方法后面再講实檀。
二惶洲、堆排序
堆排序思想是數(shù)組創(chuàng)建成堆按声，依次刪除根結(jié)點（最大元素）并放入序列直到堆空。需要注意的是堆排序可以是原地的恬吕。具體做法看代碼吧签则，主要就是刪除根時的處理，和向下調(diào)整不要寫成遞歸的铐料。
注意：上面的代碼直接手寫沒測試渐裂，可能有錯。钠惩。柒凉。理解意思就行，下面這個代碼跑過沒問題篓跛。
package fuckingtest;
import java.util.*;
public class HeapSort {
public int[] heapSort(int[] A, int n) {
int count=n-1;
build(A,count);
for(;count>0;){
int temp = A[0];
A[0]=A[count--];
down(A, count,0);
A[count+1]=temp;
}
return A;
}
void build(int[] A,int count){
for(int i=(count-1)/2;i>=0;i--){
down(A,count,i);
System.out.println(i);
}
}
void down(int[] A,int count,int i){
int r,l;
int maxson=-1;
for(;;){
l=2*i+1;
r=2*i+2;
if(r<=count){
if(A[l]>A[r])
maxson=l;
else
maxson=r;
}
else if(l<=count&&r>count)
maxson=l;
else if(l>count)
break;
if(A[maxson]>A[i]){
int temp=A[i];
A[i]=A[maxson];
A[maxson]=temp;
i=maxson;
}
else
break;
}
}
public static void main(String[] args) {
int[] r=new int[6];
int[] a=new int[]{1,5,3,4,2,6};
HeapSort h = new HeapSort();
r = h.heapSort(a,6);
for(int t:r){
System.out.println(t);
}
}
}
性能：
時間復雜度最壞平均都是O（nlogn）膝捞。原因是建堆是線性時間，然后需要連續(xù)刪除n次愧沟。額外空間復雜度O（1）（原地的）蔬咬。是不穩(wěn)定算法。雖然都是O（nlogn）級別算法沐寺，但由于快排常量系數(shù)更小林艘，最好情況更快，所以快排效率更高混坞。但堆排序的優(yōu)勢是它可以是原地的北启。
三、復雜度分析
單次插入拔第，單次刪除操作最壞情況時間復雜度O（logn）這個很好理解，那為什么建堆操作的時間復雜度是O（n）场钉？我們接下來就具體計算一下蚊俺。
為方便計算，考慮堆是滿二叉樹的情況（因為計算的是最壞情況逛万，考慮滿二叉樹也沒問題）泳猬。順著剛才講過的每層節(jié)點的交換次數(shù)想，我們計算所有節(jié)點在建堆過程中交換的次數(shù)和宇植。
假設(shè)元素個數(shù)為n得封，樹高h為㏒n。那么第x層的一個節(jié)點指郁，其深度為x忙上，高度為h-x，第x層總共有2^x個節(jié)點闲坎。
最下層非葉節(jié)點的元素疫粥，只需做一次線性運算便可以確定大根茬斧，而這一層具有2(h-1)個元素，我們假定O(1)=1梗逮，那么這一層元素所需時間為2(h-1) × 1项秉。倒數(shù)第二層最多只需要下調(diào)2次，頂點最多需要下調(diào)h次慷彤，而最后一層父節(jié)點共有2(h-1)個,倒數(shù)第二層公有2(h-2),頂點只有1(2^0)個娄蔼，
因此，可以總結(jié)出通項公式，第x層元素的計算量為2^(x) × (h-x)勇边。
又以上通項公式可得知谋币，構(gòu)造樹高為h的二叉堆的精確時間復雜度為：
S = 2^(h-1) × 1 + 2^(h-2) × 2 + …… +1 × (h-1) ①
觀察發(fā)現(xiàn)，這不就是高中時候?qū)W的數(shù)列問題嗎唉侄！該求和公式為等差數(shù)列和等比數(shù)列的乘積，因此用錯位相減發(fā)求解野建，給公式左右兩側(cè)同時乘以2属划，可知：
2S = 2^h × 1 + 2^(h-1) × 2+ …… +2 × (h-1) ②
用②減去①可知： S=2h+2(h-1)+......+2^1+1-h ③
③式是個等比數(shù)列，根據(jù)等比數(shù)列公式（別告訴我連這個都忘了候生。同眯。。）求得
S =2^h - h -1 ③
將h = ㏒n 帶入③唯鸭，S = n - ㏒n -1= O(n)
證明成功须蜗！
用這個方法，同樣可以去計算n次連續(xù)插入或n次連續(xù)刪除的時間復雜度目溉。因為n次插入和n次刪除道理是一樣的明肮，交換次數(shù)一樣，可以看成互為逆過程缭付，計算一個就行柿估，我們這里計算n次插入，更好理解些陷猫。
最下層有2^h個節(jié)點秫舌，交換h次，總結(jié)出求和公式：
S=21*1+222+......+2^hh
同樣用錯位相減法绣檬，求得S=2^(h+1)*(h-1)+2=2n(logn-1)+2=O(nlogn)
這樣建堆的時間復雜度和n次刪除的時間復雜度就都清楚了足陨。
再繼續(xù)分析建堆過程，其實如果從上往下看娇未，很像遞歸墨缘，而對這種問題，我們可以用分治法主定理來計算。
建堆算法是從最后一個非葉子結(jié)點開始下溯（向下堆化）飒房，也可以把建堆過程想成先對左子樹建堆(T(n/2))搁凸，再對右子樹建堆(T(n/2))，最后對根下溯(O(lg n))狠毯。
所以遞推式是T(n) = 2*T(n/2) + O(lg n)
根據(jù)主定理可知护糖，它的解是 T(n) = O(n)。
總結(jié)
顯然嚼松，把這個問題看作遞歸形式嫡良，套主定理公式簡單了許多。我們可以自然地想到献酗，主定理公式本質(zhì)上是不是其實就是把上面的數(shù)學推導總結(jié)成了公式寝受，也就是說我們是不是也可以用上面的方法去證明主定理？
之前遇到復雜度分析罕偎，我總是簡單記一下書上的結(jié)論很澄，只是知其然不知其所以然。主定理也只是簡單了解下颜及，沒有深入了解它的原理甩苛。其實許多問題，比如快排樞軸點為什么選擇中間的最好這些都不是很理解俏站。感覺以后不能偷懶讯蒲，還是得真正把問題弄明白。
另外感覺網(wǎng)上大部分中文資料對復雜度的數(shù)學推導不夠肄扎。比如之前搜跳表（skipList）的時候墨林，大部分博客只講了跳表的結(jié)構(gòu)，一些基本操作和特性犯祠。對于隨機的跳表節(jié)點高度為什么能證明出O(1)復雜度旭等，幾乎沒有給出數(shù)學推導的。所以最好還是手邊備一本經(jīng)典算法書衡载，并且最好習慣查英文資料
