作者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)
推 qwaszx1:謝謝大大..但是怎麼也跟答案不一樣呀? 是解答錯了嗎? 04/03 23:41
→ sunneo:因為剛開始依照你填入的陣列順序有誤 04/03 23:43
→ sunneo:題目的序列是4,2,6,5,1,7,3,8 04/03 23:44
→ sunneo:你的是4,2,6,1,3,5,7,8 04/03 23:45
推 qwaszx1:大大抱歉唷 剛發現我是用BST的方式建 左小右大 難怪會錯 04/03 23:52
→ qwaszx1:想請問第二個idx=2是怎麼算的呢? 04/03 23:53
→ sunneo:?? 算出idx = 3後就遞減直到0呀 所以當然3之後就是2了 04/03 23:54
推 qwaszx1:那您的idx=3算法跟我一樣嗎?請問[]裡的排序是指什麼呢? 04/03 23:58
→ sunneo:[]裡面是目前陣列的長相 04/03 23:58
→ qwaszx1:對不起~"~我好像真的忘得很徹底~請大大指教 謝謝您喔 04/03 23:58
→ sunneo:' '表示目前選到哪個索引上的元素 04/03 23:58
→ sunneo:不過題目說data inserted in the sequence 04/03 23:59
→ sunneo:不曉得是"已知陣列 用makeheap建立heap" 04/03 23:59
→ sunneo:還是"請以該序列(順序) 插入建立heap" 04/04 00:00
→ sunneo:兩個長法有差呢.. 04/04 00:00
推 qwaszx1:我是用以該序列(順序) 插入建立heap耶 04/04 00:02
→ qwaszx1:請問大大第一個idx=3和idx=1的[] 好像有寫錯耶^^" 04/04 00:03
推 qwaszx1:sunneo大大謝謝您讓我回想起忘記的東西 不好意思麻煩您了 04/04 00:07
※ 編輯: sunneo 來自: 61.227.121.178 (04/04 00:09)
※ 編輯: sunneo 來自: 61.227.121.178 (04/04 00:10)
→ sunneo:歐~~~我看到了 那是在複製與修改上的筆誤 04/04 00:10
推 qwaszx1:嗯嗯沒關係的 上面會問[]代表什麼就想說是不是有筆誤^^" 04/04 00:12
→ qwaszx1:真的很感激您~謝謝大大 04/04 00:12