下面的序列都是用一維陣列(1-dimension Array)來表示二元樹(Binary Tree)結構,下列何者符合最 小堆積(Minimal Heap)特性…

題目

下面的序列都是用一維陣列(1-dimension Array)來表示二元樹(Binary Tree)結構,下列何者符合最 小堆積(Minimal Heap)特性?

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