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

在區間堆中，最小元素是根節點左側的元素。此元素將被移除並返回。為了填補根節點左側產生的空缺，將從最後一個節點移除一個元素，並將其再次插入到根節點。然後，將此元素與下降節點的所有左側元素依次比較，當滿足區間堆的所有條件時，該過程終止。如果節點中的左側元素大於右側元素…… 閱讀更多

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

對稱最小-最大堆 (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) - 建立一個新的軟堆 sinsert(s, y) - 將元素 y 插入到軟堆 smeld(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 最小生成樹演算法等演算法的“可靠選擇”，並支援以下操作（假設最小堆）：find-min - 此函式負責返回堆的頂部元素。meld - 此函式負責比較兩個根元素，較小的元素保持結果的根，較大的元素及其子樹作為子節點新增…… 閱讀更多