資料結構與演算法
以根為 a[0] 的陣列表示父節點值大於或等於子節點值的最大堆積。對堆積 50, 30, 40, 10, 20, 35 加入45：先放在末尾，只要比父節點大就與父節點交換。操作後的陣列為下列何者？
- A50, 30, 40, 10, 20, 35, 45
- B45, 30, 50, 10, 20, 35, 40
- C50, 30, 45, 10, 20, 35, 40
查看答案與解析
正確答案：C. 50, 30, 45, 10, 20, 35, 40
45放在 a[6]，其父節點為 a[(6−1) ÷ 2] = a[2] = 40。由於 45 > 40，兩者交換，45移到 a[2]。下一個父節點 a[0] = 50 大於45，因此在此停止，得到 50, 30, 45, 10, 20, 35, 40。交換次數最多只有樹的高度，因此加入為 O(log n)，取出最大值也同樣是 O(log n)。由於這個性質，二元堆積常用於實作優先佇列。
- A. 只是放在末尾，雖然比父節點40大卻沒有交換。
- B. 把比根部50小的45一路移到了根部。
- C. 正確。與40交換後，父節點50較大，因此停止。