BinaryHeap.h

Go to the documentation of this file.

/*
 * $Revision: 2524 $
 *
 * last checkin:
 *   $Author: gutwenger $
 *   $Date: 2012-07-03 09:54:22 +0200 (Tue, 03 Jul 2012) $
 ***************************************************************/

#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_BINARY_HEAP_H
#define OGDF_BINARY_HEAP_H

#include<ogdf/basic/Array.h>

namespace ogdf {



// using min heaps
template <class X, class Priority=double, class INDEX=int>
class OGDF_EXPORT BinaryHeap {

public:

    class Element {

        friend class BinaryHeap<X, Priority, INDEX>;

        private:
            Priority priority;
            X elem;
            INDEX backIdx ; // the position in element array

            // empty constructor
            Element() { }

            // construct element with object and priority
            Element(X x, Priority prior) : priority(prior), elem(x) { }

            //copy constructor
            Element(const Element &origElem): priority(origElem.priority), elem(origElem.elem), backIdx(origElem.backIdx) { }

        public:

            //return the priority
            Priority getPriority() const { return priority; }

            // return reference to elem
            const X &getElement() const { return elem; }

            // return the position of this element in the heap array
            INDEX getPos() const { return backIdx; }
    };


    BinaryHeap(INDEX c) : data(1, c, 0), s(0) { }

    ~BinaryHeap() {
        for (INDEX i = 1; i <= s; ++i) {
            delete data[i];
            data[i] = 0;
        }
    }

    bool empty() const { return s == 0; }

    INDEX size() const { return s; }



    void decPriority(const Element &elem, // handle to the element
                            Priority prior // new priority, must be smaller then the old value
                            ) {
        INDEX i = elem.backIdx;

        OGDF_ASSERT(i <= s);

        if (data[i]->getPriority() < prior)
            throw "New key is greater than current key.";

        data[i]->priority = prior;
        while (i > 1 && (data[getParent(i)]->getPriority() > data[i]->getPriority()) ) {
            swap(i, getParent(i));
            i = getParent(i);
        }
    }

    const Element & insert(X obj, Priority prior) {
        Element *h_elem = new Element (obj, prior);
        ++s;
        if (s == capacity())
            data.grow(capacity(), 0); // double the size
        h_elem->backIdx = s; // store the position
        data[s] = h_elem;
        INDEX i = s;
        while ( (i > 1) && ( data[getParent(i)]->getPriority() > data[i]->getPriority()) ) {
            swap(i, getParent(i));
            i = getParent(i);
        }
        return *h_elem;
    }

    const Element & push(X obj, Priority prior) {
        return insert(obj, prior);
    }

    const X & getMin() const {
        return data[1]->getElement();
    }

    const X & top() const {
        return getMin();
    }

    X extractMin() {
        if (empty())
            throw "Heap underflow error!";

        Element copy = *data[1];
        Element *p = data[1];
        swap(1, s);
        --s;
        delete p;
        minHeapify(1);
        data[s+1] = 0;
        return copy.getElement();
    }

    X pop() {
        return extractMin();
    }

    void clear() {
        for (INDEX i = 1; i <= s; ++i) {
            delete data[i];
            data[i] = 0;
        }
        s = 0;
    }

    const X & operator[](INDEX idx) const {
        return data[idx+1]->getElement();
    }


    private :

    Array<Element *, INDEX> data; // heap array starts at index 1
    INDEX s; // current number of elements

    INDEX capacity() const { return data.size(); }

    void swap(INDEX pos1, INDEX pos2) {
        Element *tmp = data[pos1];
        data[pos1] = data[pos2];
        data[pos2] = tmp;
        // update the position
        data[pos2]->backIdx = pos2;
        data[pos1]->backIdx = pos1;
    }



    void minHeapify(INDEX pos) {
        INDEX l = getLeft(pos);
        INDEX r = getRight(pos);
        INDEX smallest;
        if (l <= size() && data[l]->getPriority() < data[pos]->getPriority() )
            smallest = l;
        else
            smallest = pos;
        if (r <= size() && data[r]->getPriority() < data[smallest]->getPriority())
            smallest = r;
        if (smallest != pos) {
            swap(pos, smallest);
            minHeapify(smallest);
        }
    }


    INDEX getParent(INDEX pos) const {return pos/2;}

    INDEX getLeft(INDEX pos) const {return pos*2;}

    INDEX getRight(INDEX pos) const {return pos*2+1;}

};

}//namespace ogdf

#endif