在某处阅读以下声明:
可以使用附加的哈希表来快速删除
最小堆。
问题>如何组合priority_queue
and 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
我必须使用列表作为容器,因为列表的迭代器不受插入/删除的影响(迭代器失效规则 https://stackoverflow.com/questions/6438086/iterator-invalidation-rules)
您无法使用提供的来执行此操作priority_queue
数据结构:
在优先级队列中,您不知道元素存储在哪里,因此很难在恒定时间内删除它们,因为您找不到元素。但是,如果您维护一个哈希表,并将优先级队列中每个元素的位置存储在哈希表中,那么您可以快速找到并删除一个项目,尽管我希望在最坏的情况下使用 log(N) 时间,而不是恒定的时间。 (我不记得你是否得到摊销常数时间。)
为此,您通常需要滚动自己的数据结构,因为每次在优先级队列中移动项目时都必须更新哈希表。
我有一些示例代码可以在这里执行此操作:
http://code.google.com/p/hog2/source/browse/trunk/algorithms/AStarOpenClosed.h 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
) 指向优先级队列中的当前位置。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)