質問: 有人會資料結構binary min-heap嗎? (a)suppose that we have implemented a binary heap using a linear array with the following keys 10,30,20,40,45,35,25,60,50.draw the result of inserting 27,17 and 7 into the heap. (b)draw the result after calling deletemin operation three times in the heap obtained from(a). (c)suppose that we take the following keys as input:150,80,40,30,10,70, 110,100,20,90,60,50,120,140,130.draw the resulting heap when the linear-time algorithm buildheap is performed.
回答: min-heap相關知識請至下面兩個網頁查閱 http://www.cs.nchu.edu.tw/~fileman/notepad/ds05.htm http://tw.knowledge.yahoo.com/question/?qid=1007111303486 (a)原本的min-heap 10 / \ 30 20 / \ / \ 40 45 35 25 / \ 60 50 加入27 10 / \ 30 20 / \ / \ 40 45 35 25 / \ / 60 50 [候選] 10 / \ 27 20 / \ / \ 40 30 35 25 / \ / \ 60 50 45 [候選] 加入17 10 / \ 17 20 / \ / \ 40 27 35 25 / \ / \ / 60 50 45 30 [候選] 加入7 7 / \ 17 10 / \ / \ 40 27 20 25 / \ / \ / 60 50 45 30 35 完成!! (b)刪除樹根3次 請參考 http://knight.fcu.edu.tw/~d9046876/ds/d_45.htm 第一次刪除7,35上來補 35 / \ 17 10 / \ / \ 40 27 20 25 / \ / \ 60 50 45 30 調整後 10 / \ 27 17 / \ / \ 40 30 20 25 / \ / \ 60 50 45 35 完成圖 27 / \ 35 30 / \ / \ 45 40 20 25 / \ 60 50 完成圖可能有錯誤,你可以自行推導比較!!~ (c)linear-time algorithm你沒有說明,所以我直接畫圖 加入40 80 / \ 150 [候選] 加入30 40 / \ 150 80 / [候選] 加入完成 30 / \ 40 80 / 150 最後完成圖 10 / \ 20 50 / \ / \ 30 40 70 110 / \ / \ / \ / \ 150 100 90 60 80 120 140 130