如何使用哈希表在最小堆上实现O（1）删除 [英] How to implement O(1) deletion on min-heap with hashtable

问题描述

在某处读取以下语句：

可以使用另一个哈希表在
min-heap中快速删除。

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

问题>如何结合 priority_queue 和 unordered_map ，以便我可以实现上述想法？

Question> How to combine priority_queue and unordered_map so that I can implement the idea above?

#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;     
}

问题>我无法进行以下工作：

Question> I am not able to make the following work:

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

我必须使用list作为容器b / c list的迭代器不受插入/删除的影响（迭代器无效规则）

I have to use list as the container b/c the iterators of list is not affected by insertion/deletion (Iterator invalidation rules)

推荐答案

您不能使用提供的 priority_queue 数据结构来做到这一点：

You can't do this with the supplied priority_queue data structure:

在优先级队列中，您不知道元素的存储位置，因此很难在恒定时间内删除它们，因为找不到元素。但是，如果维护哈希表并存储哈希表中存储的优先级队列中每个元素的位置，则可以快速查找和删除项目，尽管我希望在最坏的情况下log（N）时间不是恒定的时间。 （如果您得到了固定时间的摊销，我不会立刻想起。）

In a priority queue you don't know where the elements are stored, so it is hard to delete them in constant time, because you can't find the elements. But, if you maintain a hash table with the location of every element in the priority queue stored in the hash table, then you can find and remove an item quickly, although I would expect log(N) time in the worst case, not constant time. (I don't recall offhand if you get amortized constant time.)

为此，您通常需要滚动自己的数据结构，因为您必须更新哈希

To do this you usually need to roll your own data structures, because you have to update the hash table each time an item is moved around in the priority queue.

我有一些示例代码在这里执行此操作：

I have some example code that does this here:

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

它基于较旧的编码样式，但确实可以完成工作。

It's based on older coding styles, but it does the job.

举例说明：

/**
 * 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;
}

如果语句，我们对堆执行正常的heapify操作，然后更新哈希表中的位置（ openLocation ）以指向优先级队列中的当前位置。

Inside the if statement we do the normal heapify operations on the heap and then update the location in the hash table (openLocation) to point to the current location in the priority queue.

这篇关于如何使用哈希表在最小堆上实现O（1）删除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！