# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
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>

Inheritance diagram for ogdf::BinaryHeapSimple< X, INDEX >:

## Public Member Functions

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

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

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

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

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)].

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

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)

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

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

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

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)].

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

void heapdown ()

void heapup (INDEX idx)

## Private Attributes

Array< X, INDEXdata

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 54 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 107 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 70 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 99 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 121 of file MinHeap.h.

## ◆ heapup()

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

Definition at line 109 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 102 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 92 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 79 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 67 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 73 of file MinHeap.h.

## ◆ data

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

Definition at line 56 of file MinHeap.h.

## ◆ num

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

Definition at line 57 of file MinHeap.h.

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