如何實現對最小堆O（1）刪除與哈希表

Question

某處仔細閱讀以下聲明：

另外一個哈希表可以用來做刪除快 最小堆。

問題>如何結合priority_queue和unordered_map以便我可以實現上面的想法？

#include <queue> 
#include <unordered_map> 
#include <iostream> 
#include <list> 
using namespace std; 

struct Age 
{ 
    Age(int age) : m_age(age) {} 
    int m_age; 
}; 

// Hash function for Age 
class HashAge { 
    public: 
    const size_t operator()(const Age &a) const { 
    return hash<int>()(a.m_age); 
    } 
}; 

struct AgeGreater 
{ 
    bool operator()(const Age& lhs, const Age& rhs) const { 
    return lhs.m_age < rhs.m_age; 
    } 
}; 

int main() 
{ 
    priority_queue<Age, list<Age>, AgeGreater> min_heap;   // doesn't work 
    //priority_queue<Age, vector<Age>, AgeGreater> min_heap; 

    // Is this the right way to do it? 
    unordered_map<Age, list<Age>::iterator, HashAge > hashTable;  
} 

問題>我不能夠做了以下工作：

priority_queue<Age, list<Age>, AgeGreater> min_heap;   // doesn't work 

我必須使用列表作爲容器B/C列表的迭代器不受插入/缺失（Iterator invalidation rules ）

Answer 1

你不能提供的priority_queue數據結構做到這一點：

在優先級隊列，你不知道在哪裏的元素被存儲，所以它很難在不變的時間內刪除它們，因爲你找不到這些元素。但是，如果你用存儲在散列表中的優先級隊列中的每個元素的位置來維護一個散列表，那麼你可以快速地找到並刪除一個項目，儘管我希望在最壞的情況下log（N）時間不是常數時間。 （如果你得到一個固定的時間，我不會記得手動）

要做到這一點，你通常需要滾動你自己的數據結構，因爲每次在優先級中移動項目時都必須更新哈希表隊列。

我有一些示例代碼，這確實在這裏：

http://code.google.com/p/hog2/source/browse/trunk/algorithms/AStarOpenClosed.h

它是基於舊的編碼風格，但它的工作。

舉例說明：

/** 
* Moves a node up the heap. Returns true if the node was moved, false otherwise. 
*/ 
template<typename state, typename CmpKey, class dataStructure> 
bool AStarOpenClosed<state, CmpKey, dataStructure>::HeapifyUp(unsigned int index) 
{ 
     if (index == 0) return false; 
     int parent = (index-1)/2; 
     CmpKey compare; 

     if (compare(elements[theHeap[parent]], elements[theHeap[index]])) 
     { 
       // Perform normal heap operations 
       unsigned int tmp = theHeap[parent]; 
       theHeap[parent] = theHeap[index]; 
       theHeap[index] = tmp; 
       // Update the element location in the hash table 
       elements[theHeap[parent]].openLocation = parent; 
       elements[theHeap[index]].openLocation = index; 
       HeapifyUp(parent); 
       return true; 
     } 
     return false; 
} 

裏面的if聲明我們做堆上的正常heapify操作，然後更新哈希表（openLocation）的位置指向優先級隊列中的當前位置。