Re: [理工] [資結] Symmetric Min-Max Heaps
※ 引述《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
推
03/08 18:04, , 1F
03/08 18:04, 1F
→
03/08 18:20, , 2F
03/08 18:20, 2F
→
03/08 18:20, , 3F
03/08 18:20, 3F
推
03/08 18:20, , 4F
03/08 18:20, 4F
→
03/08 18:23, , 5F
03/08 18:23, 5F
推
03/08 18:32, , 6F
03/08 18:32, 6F
推
03/08 18:40, , 7F
03/08 18:40, 7F
推
03/08 19:29, , 8F
03/08 19:29, 8F
推
03/09 23:24, , 9F
03/09 23:24, 9F
討論串 (同標題文章)