梁　佳（青海大學(xué) 計(jì)算機(jī)技術(shù)與應(yīng)用系，青海 西寧 810016）

一種改進(jìn)的堆排序算法*

梁佳
（青海大學(xué) 計(jì)算機(jī)技術(shù)與應(yīng)用系，青海 西寧 810016）

對(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％左右。

堆排序；算法；堆重建；數(shù)據(jù)比較次數(shù)；時(shí)間復(fù)雜度

0　引言

堆實(shí)質(zhì)是一棵完全二叉樹(shù)，其任何一非葉節(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）=2n log2n+O（n）［1］，而且沒(méi)有什么最壞情況導(dǎo)致堆排序的運(yùn)行明顯變慢，同時(shí)它的空間復(fù)雜性為 O（1）［2］。排序算法的優(yōu)劣衡量標(biāo)準(zhǔn)主要由排序的時(shí)間開(kāi)銷決定，而時(shí)間開(kāi)銷主要由數(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所示。

圖1　傳統(tǒng)堆排序過(guò)程圖

在上述過(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)?，F(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　改進(jìn)的堆排序算法過(guò)程圖

2.2tail位置的確定

在上述過(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)。現(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）的值填充?，F(xiàn)在比較d與g的大小，若g大則結(jié)果如圖3（b）所示，是符合最大堆的條件的。將假設(shè)設(shè)為相反的條件，也是同理。所以只需要比較一次tail的值與父節(jié)點(diǎn)的大小即可確定tail的位置。

圖3　tail位置確定示意圖

2.3算法描述

該算法用C++語(yǔ)言描述，核心代碼如下：

template＜class T＞

void MaxHeap＜T＞::HeapSort（）

｛

createMaxHeap（arr）；//創(chuàng)建初始堆

Ttail=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=n log2n-2log2n+n。傳統(tǒng)堆排序堆重建的最多比較次數(shù)為 T=2n log2n+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=2n log2n+4n+8，已經(jīng)達(dá)到該類算法時(shí)間復(fù)雜度數(shù)量級(jí)下限，因此本文中對(duì)算法的改進(jìn)體現(xiàn)在降低算法中數(shù)據(jù)比較次數(shù)。在理論分析中改進(jìn)的算法在最壞情況下數(shù)據(jù)比較次數(shù)為 T=n log2n-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)是有效的。

圖4　傳統(tǒng)算法與改進(jì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.

An im proved heap sort algorithm

Liang Jia
（Department of Computer Technology and Applications，Qinghai University，Xining 810016，China）

This paper improved the traditional heap sort algorithmby analyzing it.Using the heap′s property to reduce comparing times in the process of heap sort，so as to improve the efficiency of the heap sort algorithm without increasing space complexity.In the process of heap rebuilt，the comparing times is half of the traditional heap sort algorithmby theoretical analysis，that is to say，the coefficient of the improved algorithm′s time complexity is half of traditional algorithm.At the same time，experimental results show that the efficiency of improved method has increased over 20％than the traditional one.

heap sort；algorithm；rebuild heap；comparing times；time complexity

TP301.6

A

1674-7720（2015）06-0010-03

2014-0-0）

梁佳（1992-），通信作者，女，本科在讀，主要研究方向：計(jì)算機(jī)科學(xué)與技術(shù)。E-mail：1054701003@qq.com。

青海大學(xué)二類課程建設(shè)項(xiàng)目《數(shù)據(jù)結(jié)構(gòu)與算法》；青海大學(xué)課程教學(xué)和考試綜合改革項(xiàng)目《數(shù)據(jù)結(jié)構(gòu)與算法》； Google 創(chuàng)新項(xiàng)目課題-基于MOOC 理念的《數(shù)據(jù)結(jié)構(gòu)與算法》課程混合教學(xué)模式研究