作者qwaszx1 (qwaszx1)
看板Grad-ProbAsk
标题[问题] 计概-heap tree
时间Fri Apr 3 18:05:45 2009
The data are inserted in the sequence of 4,2,6,5,1,7,3,8
Construct the corresponding max heap and binary search tree.
这题感觉我应该是要会建的吧!可是却觉得怪怪的@@ 请教大家一下
以下是我的(静态)算法:
4 , 2 , 6 , 5 , 1 , 7 , 3 , 8
[0] [1] [2] [3] [4] [5] [6] [7]
[0]+[7]/2=3
而建好的heap:
4
/ \
2 6
/ \ / \
1 3 5 7
\
8
而从一半开始就是从节点1开始调整
4
/ \
3 6
/ \ / \
1 2 5 7
\
8
那接下来是要调整 6,5,7吗? 可是那这样 8和7不是应该要先调整吗?
这边有点卡住了@@ 请大大指导一下
解答是给:
8
/ \
5 7
/ \ /\
4 1 6 3
/
2
先谢谢大大的指导唷
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.161.140.246
1F：→ qwaszx1:可以请各位大大帮我看一下是哪边有错吗?这题我真的不会画 04/03 22:52
2F：→ sunneo:你应该依照完整二元树的方式填入 然後1~4 shift down 04/03 23:04
3F：→ qwaszx1:嗯嗯上面第一个图是我依二元树建好的tree 但不会调整成答 04/03 23:12
4F：→ qwaszx1:案那样子的tree 请大大解惑一下 谢谢您 04/03 23:13