O（log n）攤銷時間的數據結構設計？

Question

我正在處理這個問題，但我很困惑如何解決它：

設計一個數據結構，支持以下分攤O（log n）時間的操作，其中n是總數元素：

1. 宏（K）：插入一個新的元素與密鑰K
2. 提取物 - 馬克斯：查找和最大的關鍵
3. 提取民刪除元素：找到並刪除與最小的關鍵要素
4. 聯盟：合併兩個不同ent elements of elements

如何計算攤銷時間？這不就是哈希表嗎？或者它是它的變體？ 如果有人可以幫助我，我會很感激。 謝謝！

Answer 1

你所提議的並不是大多數散列表都配備處理的，因爲散列表通常不支持在支持刪除時快速查找最小和最大元素。

但是，這個是你可以用一對支持融合的優先級隊列來做。例如，假設您使用two binomial heaps來備份數據結構 - 最小堆和最大堆。每次將元素插入到數據結構中時，都會將其添加到最小堆和最大堆中。但是，您稍微修改了兩個堆，以便堆中的每個元素都存儲一個指向其堆中對應元素的指針;這樣，給定min-heap中的節點，就可以在max-heap中找到相應的節點，反之亦然。

現在，要執行extract-min或extract-max，只需對min-heap應用find-min操作或對max-heap應用find-max操作即可獲得結果。然後，使用普通二項堆刪除操作從兩個堆中刪除該元素。 （您可以使用在插入步驟中設置的指針快速找到另一個堆中的兄弟元素）。

最後，對於聯合操作，只需將正常的二項式堆合併操作應用於相應的最小堆和最大堆。由於所有描述的操作都需要對二項堆進行O（1）操作，因此它們中的每一個在時間O（log n）最壞的情況下運行，而不需要分期付款。

一般而言，您所描述的數據結構稱爲double-ended priority queue。有幾種專門的數據結構可以用來滿足這些要求，儘管上面描述的數據結構可能是使用現成組件構建的最簡單的數據結構。