下面的序列都是用一維陣列( 1 - d i m e n s i o n A r r a y ) 來表示二元樹( B i n a r y T r e e ) 結構…

題目

下面的序列都是用一維陣列( 1 - d i m e n s i o n A r r a y ) 來表示二元樹( B i n a r y T r e e ) 結構,下列何者 符合最小堆積( M i n i m a l H e a p ) 特性?

1. (1) 1 , 10 , 5 , 6 , 7 , 8 , 9 , 2
2. (2) 1 , 5 , 10 , 6 , 7 , 8 , 9 , 2
3. (3) 1 , 2 , 8 , 5 , 3 , 9 , 10 , 6
4. (4) 1 , 5 , 3 , 2 , 9 , 8 , 6 , 10

官方答案

(3) 1 , 2 , 8 , 5 , 3 , 9 , 10 , 6

解析

最小堆積（Min Heap）要求每個父節點值皆小於或等於其子節點，且以一維陣列依層次順序存放（索引 i 的左、右子為 2i、2i+1）。檢查選項 3「1,2,8,5,3,9,10,6」：A[1]=1≤A[2]=2、A[3]=8；A[2]=2≤A[4]=5、A[5]=3；A[3]=8≤A[6]=9、A[7]=10；A[4]=5≤A[8]=6，全部滿足父≤子。其餘選項皆有父大於子的違例，故選 3。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF