BinaryHeap.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 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