作者sunneo (艾斯寇德)
看板Grad-ProbAsk
标题Re: [问题] 计概-heap tree
时间Fri Apr 3 23:36:15 2009
※ 引述《qwaszx1 (qwaszx1)》之铭言：
: 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:
以make heap, shiftdown 来做
4 [ 4 2 6 '5' 1 7 3 8 ] idx = 3
/ \ 5 < 8
2 6
/ \ / \
5 1 7 3
/
8
4 [ 4 2 '6' 8 1 7 3 5 ] idx = 2
/ \ 6 < 7
2
6
/ \ / \
8 1
7 3
/
5
4 [ 4 '2' 7 8 1 6 3 5 ] idx = 1
/ \ 2 < 8
2 7
/ \ / \
8 1 6 3
/
5
4 (调整中)
/ \ 2 < 5
8 7
/ \ / \
2 1 6 3
/
5
4 [ '4' 8 7 5 1 6 3 2 ] idx = 0
/ \ 4 < 8
8 7
/ \ / \
5 1 6 3
/
2
8 (调整中)
/ \ 4 < 5
4 7
/ \ / \
5 1 6 3
/
2
8 done
/ \
5 7
/ \ / \
4 1 6 3
/
2
以插入调整的方式来做(push back, shift up until greater than child)
4 ['4',2,6,5,1,7,3,8]
{
4 }
4 ['2',6,5,1,7,3,8]
/ { 4
2 }
2
4 ['6',5,1,7,3,8] 6 > 4
/ \ {
4 2
6 }
2
6
6 ['5',1,7,3,8] 5 > 2
/ \ { 6
2 4
5 }
2 4
/
5
6 ['1',7,3,8]
/ \ { 6 5 4 2
1 }
5 4
/ \
2
1
6 ['7',3,8] 7 > 4
/ \ { 6 5
4 2 1
7 }
5
4
/ \ /
2 1
7
6 (调整中) 7 > 6
/ \ {
6 5
7 2 1 4 }
5
7
/ \ /
2 1 4
7 ['3',8]
/ \ { 7 5 6 2 1 4
3 }
5 6
/ \ / \
2 1 4
3
7 ['8'] 8 > 2
/ \ { 7 5 6
2 1 4 3
8 }
5 6
/ \ / \
2 1 4 3
/
8
7 (调整中) 8 > 5
/ \ { 7
5 6
8 1 4 3 2 }
5 6
/ \ / \
8 1 4 3
/
2
7 (调整中) 8 > 7
/ \ { 7 8 6 5 1 4 3 2 }
8 6
/ \ / \
5 1 4 3
/
2
8 done
/ \ { 8 7 6 5 1 4 3 2 }
7 6
/ \ / \
5 1 4 3
/
2
==========================================================
void shiftdown(int a[], int idx,int size){
int up = a[ idx ];
int child;
while( idx <= size/2 ){
child = idx*2;
if( a[ child ] < a[ child+1 ] ) ++child;
if( a[ idx ] >= a[ child ] ) break;
a[ idx ] = a[ child ];
idx = child;
}
a[ idx*2 ] = up;
}
void makeheap(int a[],int size){
int i;
for(i =size/2 -1; i>=0; --i)
shiftdown(a,i,size);
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.227.121.178
※ 编辑: sunneo 来自: 61.227.121.178 (04/03 23:43)
1F：推 qwaszx1:谢谢大大..但是怎麽也跟答案不一样呀? 是解答错了吗? 04/03 23:41
2F：→ sunneo:因为刚开始依照你填入的阵列顺序有误 04/03 23:43
3F：→ sunneo:题目的序列是4,2,6,5,1,7,3,8 04/03 23:44
4F：→ sunneo:你的是4,2,6,1,3,5,7,8 04/03 23:45
5F：推 qwaszx1:大大抱歉唷 刚发现我是用BST的方式建 左小右大 难怪会错 04/03 23:52
6F：→ qwaszx1:想请问第二个idx=2是怎麽算的呢? 04/03 23:53
7F：→ sunneo:?? 算出idx = 3後就递减直到0呀 所以当然3之後就是2了 04/03 23:54
8F：推 qwaszx1:那您的idx=3算法跟我一样吗?请问[]里的排序是指什麽呢? 04/03 23:58
9F：→ sunneo:[]里面是目前阵列的长相 04/03 23:58
10F：→ qwaszx1:对不起~"~我好像真的忘得很彻底~请大大指教 谢谢您喔 04/03 23:58
11F：→ sunneo:' '表示目前选到哪个索引上的元素 04/03 23:58
12F：→ sunneo:不过题目说data inserted in the sequence 04/03 23:59
13F：→ sunneo:不晓得是"已知阵列 用makeheap建立heap" 04/03 23:59
14F：→ sunneo:还是"请以该序列(顺序) 插入建立heap" 04/04 00:00
15F：→ sunneo:两个长法有差呢.. 04/04 00:00
16F：推 qwaszx1:我是用以该序列(顺序) 插入建立heap耶 04/04 00:02
17F：→ qwaszx1:请问大大第一个idx=3和idx=1的[] 好像有写错耶^^" 04/04 00:03
18F：推 qwaszx1:sunneo大大谢谢您让我回想起忘记的东西 不好意思麻烦您了 04/04 00:07
※ 编辑: sunneo 来自: 61.227.121.178 (04/04 00:09)
※ 编辑: sunneo 来自: 61.227.121.178 (04/04 00:10)
19F：→ sunneo:欧~~~我看到了 那是在复制与修改上的笔误 04/04 00:10
20F：推 qwaszx1:嗯嗯没关系的 上面会问[]代表什麽就想说是不是有笔误^^" 04/04 00:12
21F：→ qwaszx1:真的很感激您~谢谢大大 04/04 00:12