摘 要： 對(duì)傳統(tǒng)堆排序算法進(jìn)行分析并做出改進(jìn)。利用堆的性質(zhì)降低堆排序過程中的數(shù)據(jù)比較次數(shù)，從而在不提高空間復(fù)雜度的前提下改進(jìn)了堆排序算法的效率。通過理論分析得到改進(jìn)算法在堆重建過程中的數(shù)據(jù)比較次數(shù)是傳統(tǒng)堆排序算法的一半，即改進(jìn)算法的時(shí)間復(fù)雜度的主項(xiàng)系數(shù)是傳統(tǒng)算法的1/2。同時(shí)，實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法的效率比傳統(tǒng)算法提高了20%左右。
關(guān)鍵詞： 堆排序；算法；堆重建；數(shù)據(jù)比較次數(shù)；時(shí)間復(fù)雜度
0 引言
堆實(shí)質(zhì)是一棵完全二叉樹，其任何一非葉節(jié)點(diǎn)滿足性質(zhì)：（ki≤k2i，ki≤k2i+1）或（ki≥k2i，ki≥k2i+1）（i=1，2，3，4，…，n/2）。利用堆進(jìn)行排序是一種高效的排序方法，它的時(shí)間復(fù)雜度為T（n）=2nlog2n+O（n）[1]，而且沒有什么最壞情況導(dǎo)致堆排序的運(yùn)行明顯變慢，同時(shí)它的空間復(fù)雜性為O（1）[2]。排序算法的優(yōu)劣衡量標(biāo)準(zhǔn)主要由排序的時(shí)間開銷決定，而時(shí)間開銷主要由數(shù)據(jù)的比較次數(shù)和數(shù)據(jù)移動(dòng)次數(shù)決定。理論已經(jīng)推導(dǎo)出該算法的時(shí)間復(fù)雜度已經(jīng)到達(dá)了比較排序的時(shí)間復(fù)雜度下限[3]，那么只能降低其時(shí)間復(fù)雜度的主項(xiàng)系數(shù)來提高該算法的效率。參考文獻(xiàn)[3]改進(jìn)算法與本文算法有些相似之處，但根據(jù)參考文獻(xiàn)[3]的實(shí)驗(yàn)數(shù)據(jù)可知其算法的效率提高了10%左右，而本文中效率提高達(dá)到了20%左右。王曉東在《最優(yōu)堆排序算法》一文中并沒有給出實(shí)驗(yàn)結(jié)果，只是從理論上分析了時(shí)間復(fù)雜度。王珞在《堆排序的推廣改進(jìn)》一文中雖然效率提高較大，但空間復(fù)雜度也提高了，算法也比較復(fù)雜。為此，本文在保持傳統(tǒng)算法優(yōu)點(diǎn)的前提下提出了一種簡(jiǎn)單有效的算法來提高效率，并由實(shí)驗(yàn)數(shù)據(jù)證明算法改進(jìn)的有效性。
1 問題描述
傳統(tǒng)的堆排序分為兩步：（1）根據(jù)初始輸入數(shù)據(jù)，利用堆的調(diào)整算法形成初始堆；（2）通過一系列的元素交換和重新調(diào)整堆進(jìn)行排序[2]。排序過程如圖1所示。
在上述過程中不難發(fā)現(xiàn)：每次形成最大堆后交換堆頂與堆末元素（記為tail），再逐步做下滑調(diào)整重建堆。下滑調(diào)整的目的是使大數(shù)上浮一層（即使較小的數(shù)下滑一層），在該算法中每次下調(diào)比較次數(shù)是2，移動(dòng)一次數(shù)據(jù)。在每次交換數(shù)據(jù)時(shí)，把較小的數(shù)放到最頂端，使整個(gè)序列又處于比較壞的情況，這無疑增加了許多不必要的數(shù)據(jù)移動(dòng)。那么能否為這個(gè)被交換的元素（tail）找到它合適的位置再插進(jìn)去？根據(jù)堆的性質(zhì)可以知道：堆頂?shù)脑乇灰谱吆螅碌亩秧數(shù)脑乜隙ㄊ撬淖笥易优休^大的一個(gè)。可以不交換數(shù)據(jù)，先將堆末元素取走，把堆頂元素直接放在堆末元素的位置，在它的子女中找到較大的那個(gè)子女上移一層，重復(fù)這個(gè)動(dòng)作直到葉節(jié)點(diǎn)，這樣在每一層比較中只需要比較一次。
2 算法思路與描述
2.1 改進(jìn)的算法思路
在最大堆生成后，令tail=堆末元素（即先取走堆末元素），堆頂元素放在堆末的位置，則堆頂變?yōu)榭展?jié)點(diǎn)。現(xiàn)在開始把除堆末節(jié)點(diǎn)以外的元素重建最大堆，比較空節(jié)點(diǎn)左右子女的大小，將較大的那個(gè)子女放在空節(jié)點(diǎn)的位置，取走的那個(gè)子女為新的空節(jié)點(diǎn)，重復(fù)這個(gè)動(dòng)作直到葉節(jié)點(diǎn)。將tail的值填充在空節(jié)點(diǎn)。比較原空節(jié)點(diǎn)（tail）的值與其父節(jié)點(diǎn)的大小，如果父節(jié)點(diǎn)較大則不變，反之交換兩個(gè)元素的值。
改進(jìn)的堆排序算法過程如圖2所示。
2.2 tail位置的確定
在上述過程中，需要證明一個(gè)問題，即如何在過程最后只比較一次tail的值與父節(jié)點(diǎn)的大小就可確定tail的位置。
證明過程如下。設(shè)圖3（a）中的堆為最大堆，則已知：tail=g，c>g，按照上述規(guī)則，a放在g的位置，則a為空節(jié)點(diǎn)。現(xiàn)在假設(shè)b>c，則b>g，那么b放在圖3（a）中a節(jié)點(diǎn)的位置，d、e中較大的元素放在圖3（a）中b節(jié)點(diǎn)的位置（設(shè)d較大），則現(xiàn)在圖3（a）中d節(jié)點(diǎn)的位置為空節(jié)點(diǎn)，用tail（即g）的值填充。現(xiàn)在比較d與g的大小，若g大則結(jié)果如圖3（b）所示，是符合最大堆的條件的。將假設(shè)設(shè)為相反的條件，也是同理。所以只需要比較一次tail的值與父節(jié)點(diǎn)的大小即可確定tail的位置。
2.3 算法描述
該算法用C++語言描述，核心代碼如下：
template<class T>
void MaxHeap<T>：：HeapSort（）
{
createMaxHeap（arr）；//創(chuàng)建初始堆
T tail=0；
int j=1；
for（int i=currentSize-1；i>=0；i--）
{
if（i<2）
if（heap[0]>heap[1]）
{
swap（0，1）；
break；
}
int m=0，n=1；
tail=heap[i]；//取出堆末元素
heap[i]=heap[0]；//堆頂元素放在堆末
while（n+1<i）//重建堆
{
if（heap[n]>heap[n+1]）
//找到子女中較大的使其上升
heap[m]=heap[n]；
else
{
heap[m]=heap[n+1]；
n++；}
m=n；n=2*n+1；//進(jìn)行下一個(gè)子樹的重建
}
if（tail>heap[（m-1）/2]）//確定tail的位置
{
heap[m]=heap[（m-1）/2]；
heap[（m-1）/2]=temp；
}
else heap[m]=tail；}
}；
3 算法復(fù)雜度分析與結(jié)果對(duì)比
3.1 數(shù)據(jù)移動(dòng)次數(shù)計(jì)算
本文中初始堆的建立和數(shù)據(jù)移動(dòng)次數(shù)與傳統(tǒng)算法一致，所以在此主要是比較數(shù)據(jù)的比較次數(shù)。設(shè)二叉樹有n個(gè)節(jié)點(diǎn)，對(duì)應(yīng)的完全二叉樹的深度為k=log2n+1」。每一次堆重建在二叉樹的每一層都會(huì)比較1次，所以要進(jìn)行k次比較。在整個(gè)過程中需要進(jìn)行n-2次堆的重建，所以數(shù)據(jù)需要比較k*（n-2）次，每次確定tail位置需要比較一次，共（n-2）次，在最后還需要加上兩個(gè)節(jié)點(diǎn)的情況，比較2次，所以改進(jìn)的排序算法數(shù)據(jù)比較次數(shù)為T=nlog2n-2log2n+n。傳統(tǒng)堆排序堆重建的最多比較次數(shù)為T=2nlog2n+4n+8[1]。通過兩種算法相比較可知，改進(jìn)的堆排序算法的比較次數(shù)在主項(xiàng)系數(shù)上少了一半。
3.2 實(shí)驗(yàn)結(jié)果對(duì)比
為了證實(shí)相應(yīng)的結(jié)論，比較改進(jìn)的算法與傳統(tǒng)算法之間的效率，在VC6.0環(huán)境下用rand（）函數(shù)產(chǎn)生不同量的隨機(jī)數(shù)，用QueryPerformanceFrequency（）函數(shù)獲取算法的計(jì)算時(shí)間。每組數(shù)據(jù)是測(cè)量的10組數(shù)據(jù)的平均值，做出兩種算法時(shí)間的直方圖，如圖4所示。由圖4可知，提高的效率（時(shí)間差/傳統(tǒng)算法時(shí)間）分別為18.4%、14.2%、 21.9%、19.0%、24.2%、18.6%、17.1%、15.1%，平均值為18.6%，所以效率提高了20%左右。
4 結(jié)論
通過上述分析，傳統(tǒng)的堆排序在堆重建過程中最壞情況下數(shù)據(jù)比較次數(shù)為T=2nlog2n+4n+8，已經(jīng)達(dá)到該類算法時(shí)間復(fù)雜度數(shù)量級(jí)下限，因此本文中對(duì)算法的改進(jìn)體現(xiàn)在降低算法中數(shù)據(jù)比較次數(shù)。在理論分析中改進(jìn)的算法在最壞情況下數(shù)據(jù)比較次數(shù)為T=nlog2n-2log2n+n，可以得到改進(jìn)算法在主項(xiàng)系數(shù)上為傳統(tǒng)算法的一半。通過實(shí)驗(yàn)結(jié)果對(duì)比可知，改進(jìn)算法在效率上提高了20%左右，并且該算法在空間復(fù)雜性上依舊為O（1），保持了傳統(tǒng)算法的優(yōu)點(diǎn)，表明該算法的改進(jìn)是有效的。
參考文獻(xiàn)
[1] 盧開澄.算法與復(fù)雜性[M].北京：高等教育出版社，1995.
[2] 殷人昆.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++語言描述）（第二版）[M].北京：清華大學(xué)出版社，2007.
[3] 唐開山.堆排序算法研究[J].紹興文理學(xué)院學(xué)報(bào)，2004，24（10）：16-18.