可搜索堆結構

Question

的問題是通過兩種不同的方法來訪問一系列值。首先，優先;這隻需要一堆就可以實現。此外，必須可以用一個或多個可以訪問項目列表的符號「標記」每個值。

這將是很容易的通過在兩種不同結構引用相同數據的有效實現。但是，這些必須形成一個有凝聚力的隊列。因此，通過一個結構移除的物品也必須從另一個結構中移除，這種操作堆不是非常合適。

是否有數據結構，它能夠通過一個值，以提供高效的訂貨，沒有完全降解找到在任意位置/刪除節點的性能（理想地用於推動/彈出優化）？

Answer 1

您可以從二元堆在o如果您確定要刪除哪一個刪除任何元素（日誌（n））的時間。任何節點都可以視爲有效的「子堆」，您可以像使用整個事物一樣使用delete-max（或delete-min）操作。

唯一的問題是你怎麼知道要刪除哪一個？我想我有一個解決方案。對存儲的類使用包裝器，該類包含對其堆節點的引用，並從包裝器析構函數中刪除該節點。當你想從集合中刪除任何元素時，你可以通過任何索引來刪除包裝器，它將處理其餘的部分。當您向集合中插入某些內容時，您需要創建一個包裝對象並將引用傳遞給它的堆節點。

下面是一些C++代碼：

template <class T> class Wrapper { 
    T data; 
    HeapNode* index_heap; 
    Foo* index_tags; 
    Bar* index_queue; 

    public: ~Wrapper() { 
     index_heap->delete_max(); 
     index_tags->delete_foo(); 
     index_queue->delete_bar(); 
    } 
};