具有快速隨機訪問的堆狀數據結構？

Question

我的情況是這樣的：

• 我有實體的集合，每個都有一個「善」屬性。
• 我希望一次抓一個實體，從「最好」到「最差」。
• 在獲得「最佳」實體後，我的其他實體中的幾個（相對較少）實體的「善」屬性會發生變化，而且這一變化必須納入我即將決定的下一個「最佳」實體中。
• 一些（相對較少的）實體在抓取後可能變得「毫無價值」，這些應該從我的收藏中刪除。
• 由於我剛剛抓住的實體很容易構造出一組現在「髒」的對象，也就是說，這組實體可能具有與現在不同的「優點」，或者已經成爲「不務正業」。

所以，我需要的數據結構，讓我：

• 迅速搶佔一個集合的「最大」（如，一個最大堆）。
• 快速更新我的集合中對象的基礎排序以適應上述情況。 （如果我們可以在底層堆實現中訪問髒對象的位置（例如數組索引），那麼在堆中很容易做到。）
• 有保證我的集合中的條目之間沒有衝突。 （這些條目是對上述實體的引用。）

我的想法是將max-heap與無序映射一起使用，鍵入堆條目，並且值等於，例如，堆實現中底層數組中對象的各個索引。

我想知道的是，是否可能有一個更適合這種情況的數據結構。

Answer 1

如果在抓取最佳實體時很少有成員受到影響，那麼您可以通過使用鏈表和無序映射（每個都有原始實體集合）以及最大堆來改進運行時。從鏈表最後刪除最佳實體後，您將使用映射來查找受影響的實體，將它們從列表中刪除並將非無價值的實體添加到最大堆中。此後，下一個最佳實體是列表末尾的實體或堆中的最大實體中的較大者。這種設置的優點是，從鏈表中刪除是一個恆定的時間操作，插入最大堆將是一個相對較小（相比於實體的總數）日誌時間操作。

由於實體的值只會變得更糟，您可以懶惰地將它們從鏈接列表中刪除 - 如果該項目毫無價值，則將其刪除，如果其值已更改，則將其標記爲「已更改」。檢查鏈表末尾實體上的「changed」標誌，如果它是「true」，則刪除實體並將其添加到最大堆。惰性更新的優點是，您通常不需要更新堆中的項目（您只需更新鏈接列表中項目的值），並且如果項目發生更改，然後又變得毫無價值那麼您可以將它從鏈接列表中刪除，而無需將其添加到堆中。