最小-最大堆被定義為一個完全二叉樹，包含交替的最小（或偶數）和最大（或奇數）層級。偶數層級例如 0、2、4 等，奇數層級例如 1、3、5 等。在接下來的要點中，我們認為根元素位於第一層級，即 0。最小-最大堆示例最小-最大堆的特性每個最小-最大堆中的節點都與一個數據成員（通常稱為鍵）相關聯，其值用於計算最小-最大堆中節點的順序。根元素是... 閱讀更多

Deap 被定義為一種資料結構，其根節點沒有元素或鍵值。它是透過實現以下規則形成的：根節點沒有元素，表示根節點為空。Deap 的左子樹應表示最小堆。Deap 的右子樹應表示最大堆。因此，可以透過 Deap 結構以數學方式提供以下語句的正確性：如果某個節點的左子樹和右子樹非空，並且它們的對應節點可以分別表示為“a”和“b”，則：-a.KeyValue

雙端優先佇列 (DEPQ) 或區間堆具有以下操作：isEmpty()此函式用於檢查 DEPQ 是否為空，如果為空則返回 true。size()此函式用於返回 DEPQ 中存在的元素總數。getMin()此函式用於返回具有最低優先順序的元素。getMax()此函式用於返回具有最高優先順序的元素。put(z)此函式用於將元素 z 插入 DEPQ。removeMin()此函式用於刪除具有最小優先順序的元素並返回此元素。removeMax()此函式用於刪除具有最高優先順序的元素並返回此元素。操作 isEmpty()、size()、getMin() 和 getMax() 消耗 O(1)... 閱讀更多

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

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

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

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

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

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

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