[理工] 資結 Symmetric Min-Max Heap

[ck960785 (Metal 0-4)]

 Symmetric Min-Max Heap

http://www.lib.nctu.edu.tw/n_exam/exam98/cslz/cslz1001.pdf

洪逸在2015年的資結上課有提到

Symmetric Min-Max Heap

但我沒抄到delete  Max 的Algo

請問下面的題目

刪除兩次最大值的過程為何?




題目
:                         空
:                     ／　　　＼
: 　　　　　　　  2　 　　　　     80
: 　　　　　　 ／　　＼　　　   ／　　＼
: 　　　　　　8　　   60 　    4　　　  50
: 　　　　　／ ＼　 ／　＼　 ／ ＼　  ／   ＼
:    　　  12　 20 10    16 14    30 4      40
:


Ans: 1st


:                         空
:                     ／　　　＼
: 　　　　　　　  2　 　　　　     60
: 　　　　　　 ／　　＼　　　   ／　　＼
: 　　　　　　8　　   40 　    4　　　  50
: 　　　　　／ ＼　 ／　＼　 ／ ＼　   ／
:    　　  12　 20 10    16 14    30  6



Ans : 2nd


:                         空
:                     ／　　　＼
: 　　　　　　　  2　 　　　　     50
: 　　　　　　 ／　　＼　　　   ／　　＼
: 　　　　　　8　　   40 　    4　　　  30
: 　　　　　／ ＼　 ／　＼　 ／ ＼
:    　　  12　 20 10    16 6    14

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.92.142
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1482921785.A.D6E.html
推 aa06697: 最大值會在root的右子點先刪除 為了保持complete所以同時
→ aa06697: 也刪除最後一個節點40想要插入到max值的空缺 先檢查左子
→ aa06697: 點小於等於右子點 2<=40沒問題 接著取兩者的右子點（因為
→ aa06697: 此子樹最大值必在這兩個之一) 60.50跟40比 60最大所以60
→ aa06697: 放空缺 40往下移欲插入原本60的位子 一樣檢查8<=40沒問題
→ aa06697:  取取20.16來比較 40最大 放到節點中 結束
→ aa06697: 總之就是要保持smmh的所有性質就是了（左子<=右子） root
→ aa06697: 的右點為除了root的最大值 root的左點為除了左點的最大值
→ aa06697: 洪毅上課好像沒給演算法 我是直接看聖經本內容 或上網找
→ aa06697: 應該也可以找得到演算法
謝謝 你這是第一次的結果 我回去找聖經本
※ 編輯: ck960785 (114.136.12.173), 12/29/2016 13:15:42