Re: [理工] [資結] Symmetric Min-Max Heaps

[taitin (小南)]

※ 引述《Lautreamont (Maldoror is dead)》之銘言：
: 交大98年的考題
: 3.11
: 題目:
:             *
:         /        \
:        2          80
:      /  \         / \
:     8    60     4    50
:    / \   / \   / \   / \
:   12 20 10 16 14 30 6  40
: 求刪除最小值的node之後的結果
: 下面是我爬文後看到的解答:
:              *
:         /        \
:        4          80
:      /  \         / \
:     8    60     6    50
:    / \   / \   / \   /
:   12 20 10 16 14 30 40
: 請教一下，它刪除的過程是甚麼?
: 我看題目既不是min-max heap 也不是deap
: google也沒有看到類似的說明
: 謝謝



              *
          /        \
         2          80
       /  \         / \
      8    60     4    50
     / \   / \   / \   / \
    12 20 10 16 14 30 6  40


刪除2 先由最後一個node 40來補


              *
          /        \
        40          80
       /  \         / \
      8    60     4    50
     / \   / \   / \   / \
    12 20 10 16 14 30 6


在40的下一代，以及所有堂兄弟
即 8 60 4 50中找到最小的 4

因為4<40 所以swap



              *
          /        \
        4           80
       /  \         / \
      8    60     40   50
     / \   / \   / \   / \
    12 20 10 16 14 30 6


在40的下一代，以及所有堂兄弟(同一個祖父)
即 14 30 6  找到最小 6

6<40 swap


              *
          /        \
        4           80
       /  \         / \
      8    60     6    50
     / \   / \   / \   / \
    12 20 10 16 14 30 40

final

可以參考
 Fundamentals of Data Structure

prioty queue

這題是課本例題


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.136.209.215
推 ianwuzack:原來是這樣 推~
→ assassin88:請問一下 其他的node都不用調整嗎??
→ assassin88:只要調整last node補上去那個即可??
推 Lautreamont:太感謝了 原來是這樣
→ taitin:沒有動到的都不用
推 assassin88:感謝!!
推 lovebluetea:其實和左子樹的值比就好了@@
推 stevenwin:終於會了，感謝!!
推 huming103:感謝!