c++ - 如何使用哈希表在最小堆上实现 O(1) 删除

Question

在某处阅读以下语句:

An additional hash table can be used to make deletion fast in min-heap.

问题>如何结合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) 以指向堆中的当前位置优先队列。