地圖和最小堆以獲得更好的速度

地圖和最小堆可以共同使用，從而獲得更好的攤銷時間嗎？地圖和最小堆以獲得更好的速度

讓我們假設我有一個項目，我需要跟蹤幾個項目。這些項目有一個過期的時間和一個唯一的ID：

class Item { 
    ID uid; 
    Time expiration; 
};

在這個例子中，時間和ID都是原始積分數據類型。我需要能夠通過ID快速訪問一個項目，並且我還需要能夠找到所有項目的最短到期日期。

此外，我會做大量的插入和刪除操作。

使用地圖，我會得到O（log n）的分期查找時間。（是的，我會爲此提供一個比較函數。）但是找到最小值是O（n）。

如果我使用最小堆，通過id查找時間將爲O（n），但查找最小過期爲O（1）。

在這兩種情況下，插入都是O（log n）。對於這個程序，刪除只會出現在最小項目上。

或者，我可以同時使用兩者。跟蹤相同對象的地圖和最小堆。

鑑於此設置，使用min-heap和map來避免O（n）複雜性會有好處嗎？

2010-09-28 JoshD

是的，使用雙索引可能會幫助你（給定足夠數量的項目來擊敗所涉及的常數因素）。但是，要小心 - 您需要跟蹤物品在最小堆中的位置，以便快速將其從堆中刪除。

2010-09-28 06:11:36 bdonlan

感謝您的回覆。作爲一個說明，我將刪除的唯一項目是最小堆的頂部，所以希望避免。 – JoshD 2010-09-28 06:15:18

事實上，如果你只刪除了最小堆頂部的物品，它會讓事情變得更簡單。儘管如此，還是要將迭代器保留在地圖中的位置，以減少常量因素以便刪除。 – bdonlan 2010-09-28 06:16:30

回答