我需要一个容器来储存对,我有两个操作:C++优先字典
- 更新通过关键
- 价值得到最大价值的关键。
对于第一个操作,map是一个很好的结构。对于第二个操作,似乎优先队列是一个好的队列。你会如何做到这一点?无论如何,在没有O(n)循环的情况下完成这两个操作? 谢谢。
我需要一个容器来储存对,我有两个操作:C++优先字典
对于第一个操作,map是一个很好的结构。对于第二个操作,似乎优先队列是一个好的队列。你会如何做到这一点?无论如何,在没有O(n)循环的情况下完成这两个操作? 谢谢。
渐近高效的解决方案,这将是使用哈希表和斐波那契堆的组合的最佳路线。您将使用散列表访问与O(1)时间内的任何特定键相关联的值,并使用斐波那契堆以便能够快速查找具有最低值的键/值对(这样做在O(1))。
如果要更改与某个键相关联的值,如果要增加该值,则可以在(分期偿还)O(1)时间内通过使用斐波那契堆上的增加键操作完成此操作,该操作具有O(1)摊销时间。如果你正在减少这个值,它将花费O(log n)时间从斐波那契堆中删除该元素,然后重新插入它。
总体而言,这给出了
希望这会有所帮助!
创建一个heap structure(用于第二个项目符号)并将其每个节点放置在一张地图中(对于第一个项目符号)。
编辑: 最小堆的实现我做了一段时间,在过去的
#ifndef MINHEAP_H
#define MINHEAP_H
//////////////////////// MinHeap with Map for Data ////////////////////////
template <class T, class M = int> class MinHeap {
T* array;
unsigned const int arr_max;
unsigned int elements;
M map;
void percolate_down(unsigned int i=0) {
unsigned int n = elements-1, min;
do {
unsigned int l = 2*i + 1, r = 2*i + 2;
if (l <= n && array[i] > array[l]) min = l;
else min = i;
if (r <= n && array[i] > array[r] && array[l] > array[r]) min = r;
if (i != min) {
T temp = array[i];
array[i] = array[min];
array[min] = temp;
map.update(array[i], i);
map.update(array[min], min);
i = min;
} else break;
} while (i < n);
}
void percolate_up(unsigned int i) {
while (i && array[(i-1)/2] > array[i]) {
T temp = array[i];
array[i] = array[(i-1)/2];
array[(i-1)/2] = temp;
map.update(array[i], i);
map.update(array[(i-1)/2], (i-1)/2);
i = (i-1)/2;
}
}
public:
MinHeap(const int max) : array(new T[max]), arr_max(max), elements(0), map(max) {}
~MinHeap(void) { delete[] array; }
bool empty(void) const { return elements == 0; }
unsigned int capacity(void) const { return arr_max; }
unsigned int size(void) const { return elements; }
const M& heapmap(void) const { return map; }
const T& peek(unsigned int i=0) const { return array[i]; }
bool insert(T& element) {
if (arr_max == elements) return false;
unsigned int k = elements++;
map.update(element, k);
array[k] = element;
percolate_up(k);
return true;
}
unsigned int mass_insert(T copy[], unsigned int n) {
unsigned int i = 0;
for(; i < n ; i++) if (!insert(copy[i])) break;
return i;
}
bool delete_min(void) {
if (elements == 0) return false;
map.update(array[0], arr_max+1);
array[0] = array[--elements];
map.update(array[0], 0);
percolate_down();
return true;
}
bool delete_element(unsigned int i) {
if (i > elements) return false;
map.update(array[i], arr_max+1);
T temp = array[i];
array[i] = array[--elements];
map.update(array[i], i);
if (array[i] > temp) percolate_down(i);
else if (temp > array[i]) percolate_up(i);
return true;
}
bool update(unsigned int i, T& element) {
if (i > elements) return false;
map.update(array[i], arr_max+1);
T temp = array[i];
array[i] = element;
map.update(array[i], i);
if (array[i] > temp) percolate_down(i);
else if (temp > array[i]) percolate_up(i);
return true;
}
// void print() { using namespace std; for (unsigned int i=0 ; i < elements ; i++) cout << array[i] << " | "; cout << endl; }
// Iterators
/*
friend class Const_Iterator;
class Const_Iterator {
MinHeap<T>* heap;
unsigned int index;
Const_Iterator(MinHeap<T>* h, unsigned int i) : heap(h), index(i) {}
public:
Const_Iterator(const Const_Iterator& clone) : heap(clone.heap), index(clone.index) {}
friend Const_Iterator MinHeap<T>::begin(void);
};
Const_Iterator begin(void) { return Const_Iterator(this, 0); }
*/
};
//////////////////////////////////////////////////////////////////////////////
//////////////////////// MinHeap without Map for Data ////////////////////////
template <class T> class MinHeap <T, int> {
T* array;
unsigned const int arr_max;
unsigned int elements;
void percolate_down(unsigned int i=0) {
unsigned int n = elements-1, min;
do {
unsigned int l = 2*i + 1, r = 2*i + 2;
if (l <= n && array[i] > array[l]) min = l;
else min = i;
if (r <= n && array[i] > array[r] && array[l] > array[r]) min = r;
if (i != min) {
T temp = array[i];
array[i] = array[min];
array[min] = temp;
i = min;
} else break;
} while (i < n);
}
void percolate_up(unsigned int i) {
while (i && array[(i-1)/2] > array[i]) {
T temp = array[i];
array[i] = array[(i-1)/2];
array[(i-1)/2] = temp;
i = (i-1)/2;
}
}
public:
MinHeap(const int max) : array(new T[max]), arr_max(max), elements(0) {}
~MinHeap(void) { delete[] array; }
bool empty(void) const { return elements == 0; }
unsigned int capacity(void) const { return arr_max; }
unsigned int size(void) const { return elements; }
const T& peek(unsigned int i=0) const { return array[i]; }
bool insert(T& element) {
if (arr_max == elements) return false;
unsigned int k = elements++;
array[k] = element;
percolate_up(k);
return true;
}
unsigned int mass_insert(T copy[], unsigned int n) {
unsigned int i = 0;
for(; i < n ; i++) if (!insert(copy[i])) break;
return i;
}
bool delete_min(void) {
if (elements == 0) return false;
array[0] = array[--elements];
percolate_down();
return true;
}
bool delete_element(unsigned int i) {
if (i > elements) return false;
T temp = array[i];
array[i] = array[--elements];
if (array[i] > temp) percolate_down(i);
else if (temp > array[i]) percolate_up(i);
return true;
}
bool update(unsigned int i, T& element) {
if (i > elements) return false;
T temp = array[i];
array[i] = element;
if (array[i] > temp) percolate_down(i);
else if (temp > array[i]) percolate_up(i);
return true;
}
// void print() { using namespace std; for (unsigned int i=0 ; i < elements ; i++) cout << array[i] << " | "; cout << endl; }
};
//////////////////////////////////////////////////////////////////////////////
#endif // MINHEAP_H
的boost :: bimap的可以做你想做的,在反向映射用于实现#2。
如果多个密钥的值相同,该怎么办? – templatetypedef
@templatetypedef:你的选择,可能有几个索引,比如'bimap
根据我的C++ 0x标准,The fundamental property of iterators of associative containers is that they iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct them.
所以只需使用一张地图。随机查找是O(log(n)),获得最高元素需要O(1)次。
value getHighest(map<key, value>& map) {
assert(map.empty() == false);
return (--map.end())->second;
}
这是哈希映射吗?那么查找也是O(1) – user875367
不,哈希是无序的,所以你找不到最高的元素。 –
这是一个很好的解决方案!尽管如此,你还应该注意到它们的缺点:保持它们的同步和内存使用。 –
@Minging Duck-理想情况下,你会把它包装在自己的课堂上,这样你就不会让两个人失去同步。是的,有更多的内存使用,虽然它只是一个不变的因素比只有一个结构。 – templatetypedef
@templatetypedef:+1,但斐波那契堆而不是二进制堆(或nary-heap) - 真的吗?我明白,理论上的摊销范围可能会更好,但实际情况是这样吗?参见,例如:http://stackoverflow.com/questions/504823/has-anyone-actually-implemented-a-fibonacci-heap-efficiently。另外,对于某些操作,Fibonaaci堆实际上是否具有较差的最差情况复杂度? –