申論題

四、對稱式最小-最大堆積（Symmetric Min-Max Heap，簡稱 SMMH）是一種優先佇列 （priority queue），請回答下列與 SMMH 相關的問題。

⑶請以一維陣列設計一資料結構儲存 SMMH，該資料結構可以使節點透過其對應之 陣列索引值 x 構成的數學式計算出其祖父節點 g、父節點 p、左子節點 l、右子節 點 r 與兄弟節點 s 等在陣列中的索引值。假設一維陣列之起始索引值為 0，請列出 由 x 構成之計算 g、p、l、r、s 的數學式。並請畫出以此一維陣列儲存第⑴小題建 構完成的 SMMH 的結果。（15 分）