區間堆與嵌入式最小-最大堆相同，其中每個節點包含兩個元素。它被定義為一個完全二叉樹，其中左側元素小於或等於右側元素。兩個元素都定義了一個封閉的區間。除根節點以外的任何節點所表示的區間都是父節點的子區間。左側的元素表示最小堆。右側的元素表示最大堆。根據元素數量，允許兩種情況 -偶數個元素：在這種情況下，每個節點包含兩個元素 ... 閱讀更多

在區間堆中，最小的元素是根節點左側的元素。此元素被刪除並返回。為了填充根節點左側建立的空缺，最後一個節點中的一個元素被刪除並再次插入到根節點中。然後，將此元素依次與下降節點的所有左側元素進行比較，並且當滿足區間堆的所有條件時，該過程終止。如果節點中的左側元素變得高於右側元素，則 ... 閱讀更多

根據區間堆中存在的元素數量，以下情況是可能的 -奇數個元素：如果區間堆中的元素數量為奇數，則新元素首先插入到最後一個節點中。然後，將其與前一個節點的元素依次比較，並測試以滿足區間堆所需的條件。如果元素不滿足任何條件，則將其從最後一個節點轉移到根節點，直到滿足所有條件。偶數個元素：如果元素的數量 ... 閱讀更多

對稱最小-最大堆 (SMMH) 被定義為一個完全二叉樹，其中除根節點外的每個節點都恰好有一個元素。SMMH 的根為空，SMMH 中的節點總數為 m + 1，其中 m 是元素的數量。令 y 為 SMMH 的任何節點。令 elements(y) 為以 y 為根的子樹中的元素，但不包括 y 中的元素（如果有）。假設 elements(y) j= ∅。y 滿足以下屬性：y 的左孩子在 elements(y) 中具有最小元素。y 的右孩子 ... 閱讀更多

雙端優先佇列 (DEPQ) 或雙端堆被定義為一種類似於優先佇列或堆的資料結構，但允許根據儲存在結構中的鍵或專案的某種排序有效地刪除最大值和最小值。DEPQ 中的每個元素都與一個優先順序或值相關聯。在 DEPQ 中，可以按升序和降序消除或刪除元素。操作雙端優先佇列包含以下操作isEmpty()此函式負責檢查 DEPQ 是否為空，如果為空則返回 true。size()此函式負責返回總 ... 閱讀更多

軟堆被定義為簡單堆資料結構的一個變體，它包含 5 種操作的恆定攤銷時間。這是透過仔細“破壞”（增加）堆中最多一定數量的值的鍵來獲得的。恆定時間操作為 -create(s) - 在軟堆 s 中建立一個新的軟堆insert(s,  y) - 將元素 y 插入到軟堆 s 中meld(s,  s' )將兩個軟堆 s 和 s′ 合併成一個，銷燬兩者delete(s,  y) - 從軟堆 s 中刪除元素 yfindmin(s) - 獲取軟堆中鍵值最小的元素 ... 閱讀更多

配對堆是為完美使用優先佇列而實現的。優先佇列跟蹤一組物件的最小值，因此每次我們從佇列中刪除某些內容時，它始終是最小值。在使用 Dijkstra 演算法計算圖中最短路徑時，主要實現優先佇列。配對堆很完美，因為它們易於使用並且在實際應用中執行良好。具體來說，它們在攤銷時間內執行良好。這意味著雖然單個操作消耗更長的時間，但整個操作序列中所有操作的總和 ... 閱讀更多

計算合併操作的攤銷成本是一項艱鉅的任務。主要困難在於累積在隨機操作序列的不同點執行的操作成本的巨大差異。儘管我們的設計目標受操作序列成本的影響，但根據操作序列成本來定義操作的攤銷成本的概念無濟於事。實現一個勢函式來抵消實際成本的變化是處理這種情況的完美方法。在下一個主題中，我們將討論攤銷 ... 閱讀更多

配對堆可以是空堆，也可以是包含根元素和可能為空的配對堆列表的配對樹。堆排序屬性需要任何節點的父節點都不大於節點本身。以下描述考慮了一個純函式堆，它不支援減小鍵操作。type PairingTree[Element] = Heap(element: Element, subheaps: List[PairingTree[Element]])type PairingHeap[Element] = Empty | PairingTree[Element]配對堆存在兩種型別——最小配對堆和最大配對堆。當我們希望表示最小優先佇列時，實現最小配對堆，而當我們希望表示最大優先佇列時，實現最大配對堆 ... 閱讀更多

配對堆被定義為一種堆資料結構，它具有相對簡單的實現和極佳的實際攤銷效能。配對堆是堆排序的多路樹結構，可以表示為簡化的斐波那契堆。它們被認為是實現諸如 Prim 的 MST 演算法等演算法的“穩健選擇”，並支援以下操作（假設最小堆） -find-min - 此函式負責返回堆的頂部元素。meld -此函式負責比較兩個根元素，較小的元素保持結果的根，較大的元素及其子樹作為 ... 閱讀更多