OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::BinaryHeapSimple< X, INDEX > Class Template Reference

Dynamically growing binary heap tuned for efficiency on a small interface (compared to BinaryHeap). More...

#include <ogdf/basic/MinHeap.h>

Public Member Functions

BinaryHeapSimple (INDEX size)
Construtor, giving initial array size. More...

void clear ()
empties the heap [O(1)] More...

bool empty () const
Returns true if the heap is empty. More...

extractMin ()
Returns the top (i.e., smallest) element and removed it from the heap [Same as pop(), O(log n)]. More...

const X & getMin () const
Returns a reference to the top (i.e., smallest) element of the heap. It does not remove it. [Same as top(), O(1)]. More...

void insert (X &x)
Adds an element to the heap [Same as push(), O(log n)]. More...

const X & operator[] (INDEX idx) const
obtain const references to the element at index idx (the smallest array index is 0, as for traditional C-arrays) More...

pop ()
Returns the top (i.e., smallest) element and removed it from the heap [Same as extractMin(), O(log n)]. More...

void push (X &x)
Adds an element to the heap [Same as insert(), O(log n)]. More...

INDEX size () const
Returns the number of elements in the heap. More...

const X & top () const
Returns a reference to the top (i.e., smallest) element of the heap. It does not remove it. [Same as getMin(), O(1)]. More...

Protected Member Functions

INDEX capacity () const
Returns the current array-size of the heap, i.e., the number of elements which can be added before the next resize occurs. More...

void heapdown ()

void heapup (INDEX idx)

Private Attributes

Array< X, INDEX > data

INDEX num

Detailed Description

template<class X, class INDEX = int> class ogdf::BinaryHeapSimple< X, INDEX >

Dynamically growing binary heap tuned for efficiency on a small interface (compared to BinaryHeap).

It assumes that the data-elements are themselves comparable, i.e., the compare-function of the items implicitly defines the keys. Hence this datastructure allows no key-changing operations (decreaseKey, etc.).

The heap grows (using doubling) dynamically, if there are more elements added. Furthermore, BinaryHeapSimple allows to be directly indexed using traditional array-syntax, e.g., for iterating over all its elements.

If your intended datastructure does not offer a (suitable) compare function, but you have certain key-values (scores, etc.), you may want to use the convenience-class Prioritized < Score,X > to bind both together and use within BinaryHeapSimple.

Definition at line 55 of file MinHeap.h.

◆ BinaryHeapSimple()

template<class X , class INDEX = int>
 ogdf::BinaryHeapSimple< X, INDEX >::BinaryHeapSimple ( INDEX size )
inlineexplicit

Construtor, giving initial array size.

Definition at line 61 of file MinHeap.h.

◆ capacity()

template<class X , class INDEX = int>
 INDEX ogdf::BinaryHeapSimple< X, INDEX >::capacity ( ) const
inlineprotected

Returns the current array-size of the heap, i.e., the number of elements which can be added before the next resize occurs.

Definition at line 112 of file MinHeap.h.

◆ clear()

template<class X , class INDEX = int>
 void ogdf::BinaryHeapSimple< X, INDEX >::clear ( )
inline

empties the heap [O(1)]

Definition at line 69 of file MinHeap.h.

◆ empty()

template<class X , class INDEX = int>
 bool ogdf::BinaryHeapSimple< X, INDEX >::empty ( ) const
inline

Returns true if the heap is empty.

Definition at line 64 of file MinHeap.h.

◆ extractMin()

template<class X , class INDEX = int>
 X ogdf::BinaryHeapSimple< X, INDEX >::extractMin ( )
inline

Returns the top (i.e., smallest) element and removed it from the heap [Same as pop(), O(log n)].

Definition at line 100 of file MinHeap.h.

◆ getMin()

template<class X , class INDEX = int>
 const X& ogdf::BinaryHeapSimple< X, INDEX >::getMin ( ) const
inline

Returns a reference to the top (i.e., smallest) element of the heap. It does not remove it. [Same as top(), O(1)].

Definition at line 76 of file MinHeap.h.

◆ heapdown()

template<class X , class INDEX = int>
 void ogdf::BinaryHeapSimple< X, INDEX >::heapdown ( )
inlineprotected

Definition at line 124 of file MinHeap.h.

◆ heapup()

template<class X , class INDEX = int>
 void ogdf::BinaryHeapSimple< X, INDEX >::heapup ( INDEX idx )
inlineprotected

Definition at line 114 of file MinHeap.h.

◆ insert()

template<class X , class INDEX = int>
 void ogdf::BinaryHeapSimple< X, INDEX >::insert ( X & x )
inline

Adds an element to the heap [Same as push(), O(log n)].

Definition at line 89 of file MinHeap.h.

◆ operator[]()

template<class X , class INDEX = int>
 const X& ogdf::BinaryHeapSimple< X, INDEX >::operator[] ( INDEX idx ) const
inline

obtain const references to the element at index idx (the smallest array index is 0, as for traditional C-arrays)

Definition at line 105 of file MinHeap.h.

◆ pop()

template<class X , class INDEX = int>
 X ogdf::BinaryHeapSimple< X, INDEX >::pop ( )
inline

Returns the top (i.e., smallest) element and removed it from the heap [Same as extractMin(), O(log n)].

Definition at line 94 of file MinHeap.h.

◆ push()

template<class X , class INDEX = int>
 void ogdf::BinaryHeapSimple< X, INDEX >::push ( X & x )
inline

Adds an element to the heap [Same as insert(), O(log n)].

Definition at line 81 of file MinHeap.h.

◆ size()

template<class X , class INDEX = int>
 INDEX ogdf::BinaryHeapSimple< X, INDEX >::size ( ) const
inline

Returns the number of elements in the heap.

Definition at line 66 of file MinHeap.h.

◆ top()

template<class X , class INDEX = int>
 const X& ogdf::BinaryHeapSimple< X, INDEX >::top ( ) const
inline

Returns a reference to the top (i.e., smallest) element of the heap. It does not remove it. [Same as getMin(), O(1)].

Definition at line 72 of file MinHeap.h.

◆ data

template<class X , class INDEX = int>
 Array ogdf::BinaryHeapSimple< X, INDEX >::data
private

Definition at line 57 of file MinHeap.h.

◆ num

template<class X , class INDEX = int>
 INDEX ogdf::BinaryHeapSimple< X, INDEX >::num
private

Definition at line 58 of file MinHeap.h.

The documentation for this class was generated from the following file: