題組內容

四、區間堆積（interval heap）是一種優先佇列（priority queue），請回答下列相關的問題。

(一)從一個沒有元素的區間堆積開始，依序插入 40, 30, 60, 15, 14, 19, 80, 12, 90 等元素。請畫出最後區間堆積的樹狀結構圖。（9 分）

(三)請以一維陣列設計資料結構儲存區間堆積，該資料結構可以透過節點對應之陣列索引值 index 構成的數學式計算出其父節點 parent、左子節點 left、右子節點 right 與兄弟節點 brother 等在陣列中的索引值。假設此一維陣列之起始索引值為 0，請列出由 index 構成的計算 parent、 left、right、brother 的數學式。並請畫出以此一維陣列儲存第(一)子題建構完成的區間堆積的結果。（12 分）