用堆排序方法詳見第題的分析從序列{}得到{}共用次比較其中建堆輸出比較次調堆輸出和各需要比較次和次
類似本題的另外敘述題的解答
()堆排序分析同前共+++= 次比較
對具體例子的手工堆排序略
堆與敗者樹的區別堆是n個元素的序列在向量中存儲具有如下性質
由於堆的這個性質中下標i和ii+的關系恰好和完全二叉樹中第i個結點和其子樹結點的序號間的關系一致所以堆可以看作是n個結點的完全二叉樹而敗者樹是由參加比賽的n個元素作葉子結點而得到的完全二叉樹每個非葉(雙親)結點中存放的是兩個子結點中的敗者數據而讓勝者去參加更高一級的比賽另外還需增加一個結點即結點存放比賽的全局獲勝者
()堆的存儲是順序的
()最大值元素一定是葉子結點在最下兩層上
()在建含有n個元素深度為h的堆時其比較次數不超過n推導如下
由於第i層上的結點數至多是i以它為根的二叉樹的深度為hi+則調用ën/û次篩選算法時總共進行的關鍵字比較次數不超過下式之值
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23203.html
