206
排序算法係列之堆排序
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。
1 堆排序定義
n個關鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)：(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤
)若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大於(或不小於)其左右孩子(若存在)結點的關鍵字。
下圖來自《算法導論》中堆排序一節：放到這裏幫助大家更形象的理解堆。
圖(a)是一個最大堆，圖(b)是最大堆的數組表示。
2 堆節點的訪問
通常堆是通過一維數組來實現的。在起始數組為 1 的情形中：
- 父節點i的左子節點在位置
- LEFT(i) return (2*i);
- 父節點i的右子節點在位置
- RIGHT(i) return (2*i+1);
- 子節點i的父節點在位置
- PARENT(i) return floor((i/2)）;
3 堆的操作
我們以最大堆排序來說明排序過程。
在堆的數據結構中，堆中的最大值總是位於根節點。堆中定義以下幾種操作：
- 最大堆調整（MaxHeapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點
- 創建最大堆（BuildMaxHeap）：將堆所有數據重新排序
- 堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞歸運算
4 堆排序特點
堆排序(HeapSort)是一樹形選擇排序。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關係，在當前無序區中選擇關鍵字最大(或最小)的記錄。
5 堆排序
算法動畫演示
大根堆排序實例：對於關鍵字序列(42，13，24，91，23，16，05，88)，在建堆過程中完全二叉樹及其存儲結構的變化情況。
動畫演示：【動畫演示】
堆排序c/c++實現
堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特征，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
堆操作的實現：
（1）最大堆調整MaxHeapify(A,i);
// 使以i為根的子樹成為最大堆
void MaxHeapify(int arr[],int len,int i)
{
int l = 2*i,r = 2*i+1;
int largest;
if(l<=len && arr[l]>arr[i])
largest = l;
else
largest = i;
if(r<=len && arr[r]>arr[largest])
largest = r;
if(largest != i)
{
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
MaxHeapify(arr,len,largest);
}
}
（2）創建最大堆BuildMaxHeap(A)
void BuildMaxHeap(int arr[],int len)
{
for(int i=len/2;i>=1;i--)
{
MaxHeapify(arr,len,i);
}
cout<<"build heap is ok!"<<endl;
}（3）堆排序HeapSort(A)void HeapSort(int arr[],int len)
{
BuildMaxHeap(arr,len);
printvalue(arr,len);
for(int i=len;i>=2;i--)
{
int temp = arr[1];
arr[1] = arr[i];
arr[i] = temp;
len--;
MaxHeapify(arr,len,1);
}
}
6 算法分析
堆排序的時間，主要由建立初始堆和反複重建堆這兩部分的時間開銷構成，它們均是通過調用最大堆調整MaxHeapify(A,i)實現的。堆排序的最壞時間複雜度為O(nlgn)。堆排序的平均性能較接近於最壞性能。
由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。
堆排序是就地排序，輔助空間為O(1)，
它是不穩定的排序方法。
7 堆排序與直接插入排序的區別
直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然後在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，後麵的n-2次比較中，有許多比較可能在前麵的n-1次比較中已經做過，但由於前一趟排序時未保留這些比較結果，所以後一趟排序時又重複執行了這些比較操作。堆排序可通過樹形結構保存部分比較結果，可減少比較次數。
8 參考文章
2.堆排序基礎講解：https://www.wutianqi.com/?p=1820；
3.算法導論學習總結：https://www.wutianqi.com/?p=2343；
9 整體代碼（包括實驗程序C++）
#include <cstdlib>
#include <iostream>
using namespace std;
void printvalue(int arr[],int len)
{
int i;
cout<<"the arr value:";
for(i=1;i<=len;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
void MaxHeapify(int arr[],int len,int i)
{
int l = 2*i,r = 2*i+1;
int largest;
if(l<=len && arr[l]>arr[i])
{
largest = l;
}
else
{
largest = i;
}
if(r<=len && arr[r]>arr[largest])
{
largest = r;
}
if(largest != i)
{
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
MaxHeapify(arr,len,largest);
}
}
void BuildMaxHeap(int arr[],int len)
{
for(int i=len/2;i>=1;i--)
{
MaxHeapify(arr,len,i);
}
cout<<"build heap is ok!"<<endl;
}
void HeapSort(int arr[],int len)
{
BuildMaxHeap(arr,len);
printvalue(arr,len);
for(int i=len;i>=2;i--)
{
int temp = arr[1];
arr[1] = arr[i];
arr[i] = temp;
len--;
MaxHeapify(arr,len,1);
}
}
int main(int argc, char *argv[])
{
int a[100];
int len =88;
for(int i=1;i<=len;i++) //88個數
{
a[i] = len - i + 1;
}
cout<<"init a[]:";
printvalue(a,len);
cout<<endl;
HeapSort(a,len);
cout<<"After HeapSort!"<<endl;
printvalue(a,len);
system("PAUSE");
return EXIT_SUCCESS;
}
最後更新：2017-04-03 18:52:08