Open
Graph Drawing
Framework

 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.

Constructor & Destructor Documentation

◆ 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.

Member Function Documentation

◆ 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.

Member Data Documentation

◆ data

template<class X , class INDEX = int>
Array<X,INDEX> 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: