Re: [問題] 計概-heap tree
※ 引述《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)
推
04/03 23:41, , 1F
04/03 23:41, 1F
→
04/03 23:43, , 2F
04/03 23:43, 2F
→
04/03 23:44, , 3F
04/03 23:44, 3F
→
04/03 23:45, , 4F
04/03 23:45, 4F
推
04/03 23:52, , 5F
04/03 23:52, 5F
→
04/03 23:53, , 6F
04/03 23:53, 6F
→
04/03 23:54, , 7F
04/03 23:54, 7F
推
04/03 23:58, , 8F
04/03 23:58, 8F
→
04/03 23:58, , 9F
04/03 23:58, 9F
→
04/03 23:58, , 10F
04/03 23:58, 10F
→
04/03 23:58, , 11F
04/03 23:58, 11F
→
04/03 23:59, , 12F
04/03 23:59, 12F
→
04/03 23:59, , 13F
04/03 23:59, 13F
→
04/04 00:00, , 14F
04/04 00:00, 14F
→
04/04 00:00, , 15F
04/04 00:00, 15F
推
04/04 00:02, , 16F
04/04 00:02, 16F
→
04/04 00:03, , 17F
04/04 00:03, 17F
推
04/04 00:07, , 18F
04/04 00:07, 18F
※ 編輯: sunneo 來自: 61.227.121.178 (04/04 00:09)
※ 編輯: sunneo 來自: 61.227.121.178 (04/04 00:10)
→
04/04 00:10, , 19F
04/04 00:10, 19F
推
04/04 00:12, , 20F
04/04 00:12, 20F
→
04/04 00:12, , 21F
04/04 00:12, 21F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：