847
數據結構之堆排序
在數據結構中,堆排序是非常重要的一個知識點,尤其像在期末考試、考研等計算機考試中經常會考察堆排序,並要求畫出示意圖.下麵主要通過一道考研題目講述堆排序的知識,希望對大家有所幫助.
(文章內容參考嚴蔚敏的《數據結構》、王道論壇的《數據結構》和自己的一些理解)
參看動態圖：https://www.benfrederickson.com/heap-visualization/
一.堆排序定義
堆排序是一種樹形選擇排序方法,它的特點是在排序過程中,將L[1...n]看成一顆完全二叉樹的順序存儲結果,利用完全二叉樹中雙親結點和孩子結點之間的內在關係,在當前無序區中選擇關鍵字最大或最小的元素.該算法時間複雜度O(nlong2n),是不穩定排序.
堆的定義:n個元素的序列K[1..n]當且僅當滿足:
(1).K[i]<=K[2i]且K[i]<=K[2i+1] 或 (2).K[i]>=K(2i)且K[i]>=K[2i+1] (i=1,2...|_n/2_|)
如下圖所示:
滿足(1)的堆稱為小根堆,滿足(2)的堆稱為大根堆.
在大根堆中,堆頂元素(完全二叉樹的根)必為序列中n個元素的最大值,且對其任一非根結點,它的值不大於其雙親結點值.對應的是最大堆.同理,小根堆定義相反,根節點為最小值.如下圖分別是最大堆和最小堆.堆采用的存儲方式是順序存儲結構.
二.堆排序實現
堆排序利用堆的特性進行排序,其基本思想是:首先將待排序的記錄序列構造成一個堆;然後選出對中所有記錄的最小值(最小堆);再把它從堆中輸出,並把剩餘的元素排成最小堆,依次找次小的記錄並輸出,直到隻有一個記錄為止.問題的步驟為:
(1).如何從一個無序序列初始建堆,這是堆排序的關鍵.(初始建堆)
(2).如何處理堆頂記錄.(處理堆頂)
(3).輸出堆頂元素後如何調整剩餘元素,構建一個新堆.(重新建堆)
例:(改考研題)使用堆排序對序列{38,49,13,97,27,76,65,50}進行排序,要求畫出最小堆,並畫出堆排序的示意圖.
首先按照題目順序構造一個完全二叉樹如下圖所示,然後按照下麵的"初始建堆"和"堆排序"實現.
1.初始建堆
對初始序列建堆,就是有一個反複篩選的過程.n個結點的完全二叉樹,最後一個結點是第|_n/2_|(其中|_x_|表示不大於x的最大整數)個結點的孩子.小根堆其基本思想從|_n/2_|根節點開始,盡量讓最小數向二叉樹根結點(堆頂)移動,使子樹都成為堆.
(1).對第|_n/2_|個結點為根的子樹篩選,對於小根堆：如果根結點的關鍵字大於左右子女結點中關鍵字較小者,則交換,使子樹成為堆.
題中：i=|_8/2_|=4,指向97根結點,大於其左孩子結點50,故交換順序.如下圖.
(2).然後向前依次對各結點(|_n/2_|-1到1)為根的子樹進行篩選,看該結點值是否小於其左右子結點,如果不是,將左右子結點中較小者與之交換;交換後可能會破壞下一級的堆,繼續采用上述方法構造下一級的堆,直到該結點為根的子樹構成堆位置.
(3).反複使用上述方法建堆,直到根節點.題中根節點交換時亦要檢查器下級堆是否要交換順序.
2.堆排序
在使用完全二叉樹初始建立好如上圖的最小堆後,就是對該堆進行排序輸出.此時的算法是:
(1).輸出堆頂元素,題中堆頂元素=13;輸出後以堆中最後一個元素=97替代堆頂元素;然後將根節點值與左右子樹的根節點進行比較,並與其中小者進行交換;
(2).重複上述操作,直到葉子節點,將得到的新堆稱為這個從堆頂至葉子的調整過程為"篩選".
輸出堆頂27,將最後一個元素65替代堆頂元素,再從49和38中選擇較小值38,將65與38元素交換.(答題是隻畫最後交換好的再配上必要文字說明即可)
輸出堆頂38,將最後一個元素76替代堆頂元素,再根據方法依次交換76與49,76與50.
輸出堆頂49,將最後一個元素97替代堆頂元素,再根據方法依次交換97與50,97與76.
同理一次輸出如下:
三.總結
該文章主要是解決上麵的那個堆排序問題,而相應的算法代碼和插入刪除亦類似沒給出.寫這篇文章主要是紀念自己這幾個月考研的日子,同時無論考研結果如何,都要在考完後學習更多自己感興趣的編程知識,並完成一些自己感興趣的工程和博客.這才是我想要的東西.最後希望該文章對大家有所幫助,尤其是考研的學子.希望大家考研順利,同時如果文章中有錯誤或不足之處,希望大家海涵!
(BY:Eastmount 2013-12-17 下午4點 https://blog.csdn.net/eastmount/)
最後更新：2017-04-03 12:53:45