bheap.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/lib/abacus/abacusroot.h>
 
 
namespace abacus {
 
template<class Type, class Key>
class AbaBHeap;
 
template<class Type,class Key>
std::ostream&operator<< (std::ostream& out, const AbaBHeap<Type, Key>& heap);
 
 
 
template<class Type, class Key> class  AbaBHeap :  public AbacusRoot  {
public:
 
 
    explicit AbaBHeap(int size);
 
 
    AbaBHeap(
        const ArrayBuffer<Type> &elems,
        const ArrayBuffer<Key> &keys);
 
 
    friend std::ostream& operator<< <> (std::ostream &out, const AbaBHeap<Type, Key> &heap);
 
 
    void insert(Type elem, Key key);
 
 
    Type getMin() const;
 
 
    Key getMinKey() const;
 
 
    Type extractMin();
 
 
    void clear();
 
    int size() const;
 
    int number() const;
 
    bool empty() const;
 
 
    void realloc(int newSize);
 
 
    void check() const;
 
private:
 
    int  leftSon(int i) const;
 
    int  rightSon(int i) const;
 
    int  father(int i) const;
 
 
    void heapify(int i);
 
    Array<Type>  heap_;
    Array<Key>   keys_;
    int          n_;
};
 
}
 
#include <ogdf/lib/abacus/bheap.inc>