C ++ priority dictionary

Question

I need a container for storing steam, I have two operations:

• key update value
• get the key with the maximum value.

For the first operation, the map is a good structure. For the second operation, it seems that the priority queue is good. How would you do that? Is there anyway two operations performed without an O (n) loop? Thanks.

Answer 1

An asymptotically effective solution for this would be to use a combination of a hash table and a Fibonacci heap. You would use a hash table to be able to access the value associated with a particular key in O (1) time, and use the Fibonacci heap to be able to quickly look up the key / value pair with the smallest value (by doing this in O (1)).

If you want to change the value associated with the key, if you increase the value, you can do it ((amortized) O (1) times using the operation of increasing the key in the Fibonacci heap, which has O (1) amortized time. If you decrease the value, it will take O (log n) time to remove the item from the Fibonacci heap, then reinsert it.

All in all, this gives temporary complexity.

• Insert a new element: O (1) for hash, O (1) to insert into the Fibonacci heap: O (1) time .
• Delete item: O (1) for hash, O (log n) to remove from the Fibonacci heap: O (log n) time .
• Find the top element: O (1) to search in the Fibonacci heap: O (1) time.
• Increase the value: O (1) for the hash, O (1) for the increase key: O (1).
• Decrease the value: O (1) for the hash, O (log n) for delete / insert: O (log n).

Hope this helps!

Answer 2

Create a heap structure (for the second bullet) and place each node on the map (for the first bullet).

EDIT: The mini-heap implementation I've done in the past

#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 

Answer 3

boost :: bimap can do what you want, where the reverse map is used to implement # 2.

Answer 4

According to my C ++ 0x standard, 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.

So just use the card. A random search is O (log (n)) and it takes O (1) time to get the highest element.

 value getHighest(map<key, value>& map) { assert(map.empty() == false); return (--map.end())->second; } 

Answer 5

I think bimap is the best route