關係資料結構

全元素對應和葉元素對應是更為複雜的關係技術。這兩種技術中，一半元素位於最小優先順序佇列，另一半元素位於最大優先順序佇列。如果元素數量為奇數，則一個元素儲存在緩衝區中。該緩衝元素既不屬於最小優先順序佇列，也不屬於最大優先順序佇列。在全元素對應技術中，最小優先順序佇列中的每個元素 x 都與最大優先順序佇列中的一個不同元素 y 配對。(x, y) 是元素的一對對應元組，其中 priority(x) <= priority(y)。

圖 E 顯示了 11 個元素 3、4、5、5、6、6、7、8、9、10、11 的全元素對應堆。元素 10 位於緩衝區。對應元組由紅色箭頭表示。

圖 E：全元素對應堆

在葉元素對應技術中，最小優先順序佇列和最大優先順序佇列的每個葉元素都需要成為一對對應元組的一部分。非葉元素不需要屬於任何對應元組。圖 F 顯示了葉元素對應堆。

圖 F：葉元素對應堆

全元素對應和葉元素對應結構所需的空間比對偶結構少。但是，全元素對應和葉元素對應結構的 DEPQ 演算法比對偶結構更為複雜。在三種對應技術中，葉元素對應是最快的 DEPQ 對應結構。

Arnab Chakraborty

更新於：2020 年 1 月 3 日

已瀏覽 322 次

開啟您的 職業

完成課程即可獲得認證

開始