MinHeap.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/comparer.h>
 
namespace ogdf {
 
 
template<class X, class INDEX = int>
class BinaryHeapSimple {
private:
    Array<X, INDEX> data; // array starts at index 1
    INDEX num;
 
public:
    explicit BinaryHeapSimple(INDEX size) : data(1, size), num(0) { }
 
    bool empty() const { return num == 0; }
 
    INDEX size() const { return num; }
 
    void clear() { num = 0; }
 
    const X& top() const { return data[1]; }
 
    inline const X& getMin() const { return top(); }
 
    void push(X& x) {
        X y;
        if (num == capacity()) {
            data.grow(capacity(), y); // double the size & init with nulls
        }
        data[++num] = x;
        heapup(num);
    }
 
    inline void insert(X& x) { push(x); }
 
    X pop() {
        data.swap(1, num--);
        heapdown();
        return data[num + 1];
    }
 
    inline X extractMin() { return pop(); }
 
    const X& operator[](INDEX idx) const { return data[idx + 1]; }
 
 
protected:
    INDEX capacity() const { return data.size(); }
 
    void heapup(INDEX idx) {
        INDEX papa;
        while ((papa = idx / 2) > 0) {
            if (data[papa] > data[idx]) {
                data.swap(papa, idx);
                idx = papa;
            } else {
                return; //done
            }
        }
    }
 
    void heapdown() {
        INDEX papa = 1;
        INDEX son;
        while (true) {
            if ((son = 2 * papa) < num && data[son + 1] < data[son]) {
                son++;
            }
            if (son <= num && data[son] < data[papa]) {
                data.swap(papa, son);
                papa = son;
            } else {
                return;
            }
        }
    }
};
 
 
template<class X, class INDEX = int>
class Top10Heap : protected BinaryHeapSimple<X, INDEX> { // favors the 10 highest values...
public:
    enum class PushResult { Accepted, Rejected, Swapped };
 
    static bool successful(PushResult r) { return r != PushResult::Rejected; }
 
    static bool returnedSomething(PushResult r) { return r != PushResult::Accepted; }
 
    Top10Heap() : BinaryHeapSimple<X, INDEX>(10) { }
 
    using BinaryHeapSimple<X, INDEX>::BinaryHeapSimple;
 
    bool full() const { return size() == capacity(); }
 
    using BinaryHeapSimple<X, INDEX>::empty;
    using BinaryHeapSimple<X, INDEX>::size;
    using BinaryHeapSimple<X, INDEX>::capacity;
    using BinaryHeapSimple<X, INDEX>::clear;
    using BinaryHeapSimple<X, INDEX>::top;
 
 
    PushResult push(X& x, X& out) {
        // returns element that got kicked out -
        // out is uninitialized if heap wasn't full (i.e. PushResult equals Accepted)
        PushResult ret = PushResult::Accepted;
        if (capacity() == size()) {
            if (BinaryHeapSimple<X, INDEX>::top() >= x) { // reject new item since it's too bad
                out = x;
                return PushResult::Rejected;
            }
            out = BinaryHeapSimple<X, INDEX>::pop(); // remove worst first
            ret = PushResult::Swapped;
        }
        BinaryHeapSimple<X, INDEX>::push(x);
        return ret;
    }
 
    inline PushResult insert(X& x, X& out) { return push(x, out); }
 
 
    void pushBlind(X& x) {
        if (capacity() == size()) {
            if (BinaryHeapSimple<X, INDEX>::top() >= x) { // reject new item since it's too bad
                return;
            }
            BinaryHeapSimple<X, INDEX>::pop(); // remove worst first
        }
        BinaryHeapSimple<X, INDEX>::push(x);
    }
 
    inline void insertBlind(X& x) { pushBlind(x); }
 
 
    const X& operator[](
            INDEX idx) const { // ATTN: simulate index starting at 0, to be "traditional" to the outside!!!
        return BinaryHeapSimple<X, INDEX>::operator[](idx);
    }
};
 
 
template<class X, class Priority = double, class STATICCOMPARER = StdComparer<X>, class INDEX = int>
class DeletingTop10Heap : public Top10Heap<Prioritized<X*, Priority>, INDEX> {
public:
    explicit DeletingTop10Heap(int size) : Top10Heap<Prioritized<X*, Priority>, INDEX>(size) { }
 
 
    void pushAndDelete(X* x, Priority p) {
        Prioritized<X*, Priority> vo;
        Prioritized<X*, Priority> nv(x, p);
        if (this->returnedSomething(Top10Heap<Prioritized<X*, Priority>, INDEX>::push(nv, vo))) {
            delete vo.item();
        }
    }
 
    inline void insertAndDelete(X* x, Priority p) { pushAndDelete(x, p); }
 
 
    void pushAndDeleteNoRedundancy(X* x, Priority p) {
        for (INDEX i = Top10Heap<Prioritized<X*, Priority>, INDEX>::size(); i-- > 0;) {
            X* k = Top10Heap<Prioritized<X*, Priority>, INDEX>::operator[](i).item();
#if 0
            OGDF_ASSERT(x);
            OGDF_ASSERT(k);
#endif
            if (TargetComparer<X, STATICCOMPARER>::equal(k, x)) {
                delete x;
                return;
            }
        }
        pushAndDelete(x, p);
    }
 
    inline void insertAndDeleteNoRedundancy(X* x, Priority p) { pushAndDeleteNoRedundancy(p, x); }
};
 
}