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

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

雙端優先佇列 (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 的任何節點。設 elements(y) 為以 y 為根的子樹中的元素，但不包括 y 中的元素（如果有）。假設 elements(y) j= ∅。y 滿足以下屬性：y 的左子節點在 elements(y) 中具有最小元素。y 的右子節點... 閱讀更多

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

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

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