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