在資料結構中,堆排序是非常重要的一個知識點,尤其像在期末考試、考研等計算機考試中經常會考察堆排序,并要求畫出示意圖.下面主要通過一道考研題目講述堆排序的知識,希望對大家有所幫助.
(文章内容參考嚴蔚敏的《資料結構》、王道論壇的《資料結構》和自己的一些了解)
堆排序是一種樹形選擇排序方法,它的特點是在排序過程中,将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}進行排序,要求畫出最小堆,并畫出堆排序的示意圖.
首先按照題目順序構造一個完全二叉樹如下圖所示,然後按照下面的"初始建堆"和"堆排序"實作.
對初始序列建堆,就是有一個反複篩選的過程.n個結點的完全二叉樹,最後一個結點是第|_n/2_|(其中|_x_|表示不大于x的最大整數)個結點的孩子.小根堆其基本思想從|_n/2_|根節點開始,盡量讓最小數向二叉樹根結點(堆頂)移動,使子樹都成為堆.
(1).對第|_n/2_|個結點為根的子樹篩選,對于小根堆：如果根結點的關鍵字大于左右子女結點中關鍵字較小者,則交換,使子樹成為堆.
題中：i=|_8/2_|=4,指向97根結點,大于其左孩子結點50,故交換順序.如下圖.
(2).然後向前依次對各結點(|_n/2_|-1到1)為根的子樹進行篩選,看該結點值是否小于其左右子結點,如果不是,将左右子結點中較小者與之交換;交換後可能會破壞下一級的堆,繼續采用上述方法構造下一級的堆,直到該結點為根的子樹構成堆位置.
(3).反複使用上述方法建堆,直到根節點.題中根節點交換時亦要檢查器下級堆是否要交換順序.
在使用完全二叉樹初始建立好如上圖的最小堆後,就是對該堆進行排序輸出.此時的算法是:
(1).輸出堆頂元素,題中堆頂元素=13;輸出後以堆中最後一個元素=97替代堆頂元素;然後将根節點值與左右子樹的根節點進行比較,并與其中小者進行交換;
(2).重複上述操作,直到葉子節點,将得到的新堆稱為這個從堆頂至葉子的調整過程為"篩選".
輸出堆頂27,将最後一個元素65替代堆頂元素,再從49和38中選擇較小值38,将65與38元素交換.(答題是隻畫最後交換好的再配上必要文字說明即可)
輸出堆頂38,将最後一個元素76替代堆頂元素,再根據方法依次交換76與49,76與50.
輸出堆頂49,将最後一個元素97替代堆頂元素,再根據方法依次交換97與50,97與76.
同理一次輸出如下:
該文章主要是解決上面的那個堆排序問題,而相應的算法代碼和插入删除亦類似沒給出.寫這篇文章主要是紀念自己這幾個月考研的日子,同時無論考研結果如何,都要在考完後學習更多自己感興趣的程式設計知識,并完成一些自己感興趣的工程和部落格.這才是我想要的東西.最後希望該文章對大家有所幫助,尤其是考研的學子.希望大家考研順利,同時如果文章中有錯誤或不足之處,希望大家海涵!