C++ priority dictionary

Question

I need a container to store pairs, I have two operations:

update value by key
get the key with maximum value.

For the first operation, map is a good structure. For the second operation, seems priority queue is a good one. How would you do this? Is there anyway to have both of the two operations done without having a O(n) loop? Thanks.

score 7 · Accepted Answer · answered Aug 30 '11 at 23:01

7

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

If you want to change the value associated with a key, if you are increasing the value, you can do so in (amortized) O(1) time by using the increase-key operation on the Fibonacci heap, which has O(1) amortized time. If you are decreasing the value, it will take O(log n) time to delete the element out of the Fibonacci heap and then reinsert it.

Overall, this gives a time complexity of

Insert a new element: O(1) for hash, O(1) for insert into Fibonacci heap: O(1) time.
Delete an element: O(1) for hash, O(log n) for delete from Fibonacci heap: O(log n) time.
Find top element: O(1) for lookup in Fibonacci heap: O(1) time.
Increase a value: O(1) for hash, O(1) for increase-key: O(1) time.
Decrease a value: O(1) for hash, O(log n) for delete/insert: O(log n) time.

Hope this helps!

answered Aug 30 '11 at 23:01

templatetypedef

362,284
104
897
1,065

This is a good solution! You should note downsides too though: keeping them synchronized, and memory usage. – Mooing Duck Aug 31 '11 at 00:32
@Mooing Duck- Ideally, you would wrap this up in its own class so that you couldn't get the two out of sync with one another. And yes, there's more memory usage, though it's only a constant factor more than having only one of the two structures. – templatetypedef Aug 31 '11 at 00:35
1

@templatetypedef: +1, but a Fibonacci heap rather than a binary-heap (or nary-heap) - really? I understand that the theoretical amortised bounds may be better, but is this the case practically? See, for instance: http://stackoverflow.com/questions/504823/has-anyone-actually-implemented-a-fibonacci-heap-efficiently. Also, don't Fibonaaci heaps actually have poor worst case complexity for some operations? – Darren Engwirda Aug 31 '11 at 01:16
1

@Darren Engwirda- Fibonacci heaps do have bad worst-case performance, but excellent amortized performance. If you must guarantee that each operation is fast, a Brodal queue would also work. And yes, Fibonacci heaps can be slower than binary heaps. This solution is *asymptotically* good, but might not be that fast in practice unless the data set is pretty big. – templatetypedef Aug 31 '11 at 01:18
@templatetypedef: LOL at constant factor more than one structure, for something _asymptotically_ good rather than practically good. – Mooing Duck Aug 31 '11 at 02:41

score 3 · Answer 2 · answered Aug 30 '11 at 22:57

Create a heap structure (for the second bullet) and put each of its nodes in a map (for the first bullet).

EDIT: An implementation of min heap I had done some time 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

@Toolbox A heap structure is a way to implement a priority_queue :) — George Kastrinis, Aug 30 '11 at 23:01
I know -- what I meant was that there's no need to re-implement what's already part of standard C++. — Dawson, Aug 30 '11 at 23:03

score 2 · Answer 3 · answered Aug 30 '11 at 22:58

2

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

answered Aug 30 '11 at 22:58

goffrie

461
2
7

What if multiple keys have the same value? – templatetypedef Aug 30 '11 at 23:06
@templatetypedef: your choice, several indexes are possible, like `bimap >`. – Matthieu M. Aug 31 '11 at 06:20

score 1 · Answer 4 · answered Aug 30 '11 at 23:11

1

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 a map. Random lookup is O(log(n)), and to get the highest element takes O(1) time.

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

answered Aug 30 '11 at 23:11

Mooing Duck

64,318
19
100
158

Is this hold for hash map? then lookup would also be O(1) – user875367 Aug 30 '11 at 23:54
No, hashes are unordered, so you can't find the highest element. – Mooing Duck Aug 31 '11 at 00:31

score 0 · Answer 5 · answered Aug 30 '11 at 23:01

0

I think the bimap is the best route

answered Aug 30 '11 at 23:01

Ed Heal

59,252
17
87
127

What if multiple keys have the same value associated with them? – templatetypedef Aug 30 '11 at 23:06

C++ priority dictionary

5 Answers5