堆與堆排序

堆排序與快速排序，歸並排序一樣都是時間復雜度為O(N*logN)的幾種常見排序方法。學習堆排序前，先講解下什麼是數據結構中的二叉堆。

二叉堆的定義

二叉堆是完全二叉樹或者是近似完全二叉樹。

二叉堆滿足二個特性：

1．父結點的鍵值總是大於或等於（小於或等於）任何一個子節點的鍵值。

2．每個結點的左子樹和右子樹都是一個二叉堆（都是最大堆或最小堆）。

當父結點的鍵值總是大於或等於任何一個子節點的鍵值時為最大堆。當父結點的鍵值總是小於或等於任何一個子節點的鍵值時為最小堆。下圖展示一個最小堆：

由於其它幾種堆（二項式堆，斐波納契堆等）用的較少，一般將二叉堆就簡稱為堆。

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm

堆的存儲

一般都用數組來表示堆，i結點的父結點下標就為(i – 1) / 2。它的左右子結點下標分別為2 * i + 1和2 * i + 2。如第0個結點左右子結點下標分別為1和2。

堆的操作——插入刪除

下面先給出《數據結構C++語言描述》中最小堆的建立插入刪除的圖解，再給出本人的實現代碼，最好是先看明白圖後再去看代碼。

《數據結構 C++ 語言描述》(Data Structures C++ ) PDF 下載地址：http://www.linuxidc.com/Linux/2014-09/107319.htm

堆的插入

每次插入都是將新數據放在數組最後。可以發現從這個新數據的父結點到根結點必然為一個有序的數列，現在的任務是將這個新數據插入到這個有序數據中——這就類似於直接插入排序中將一個數據並入到有序區間中，對照《直接插入排序的三種實現》不難寫出插入一個新數據時堆的調整代碼：

// 新加入i結點 其父結點為(i - 1) / 2

void MinHeapFixup(int a[], int i)

{

int j, temp;

temp = a[i];

j = (i - 1) / 2; //父結點

while (j >= 0)

{

if (a[j] <= temp)

break;

a[i] = a[j]; //把較大的子結點往下移動,替換它的子結點

i = j;

j = (i - 1) / 2;

}

a[i] = temp;

}

更簡短的表達為：

void MinHeapFixup(int a[], int i)

{

for (int j = (i - 1) / 2; j >= 0 && a[i] > a[j]; i = j, j = (i - 1) / 2)

Swap(a[i], a[j]);

}

插入時：

//在最小堆中加入新的數據nNum

void MinHeapAddNumber(int a[], int n, int nNum)

{

a[n] = nNum;

MinHeapFixup(a, n);

}

更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2014-09/107318p2.htm