Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

abacus::AbaBHeap< Type, Key > Class Template Reference

Binary heaps. More...

#include <ogdf/lib/abacus/bheap.h>

Public Member Functions

 AbaBHeap (const ArrayBuffer< Type > &elems, const ArrayBuffer< Key > &keys)
 A constructor with initialization. More...
 
 AbaBHeap (int size)
 A constructor. More...
 
void check () const
 Throws an exception if the heap properties are violated. More...
 
void clear ()
 Empties the heap. More...
 
bool empty () const
 Return true if there are no elements in the heap, false otherwise. More...
 
Type extractMin ()
 Accesses and removes the minimum element from the heap. More...
 
Type getMin () const
 Returns the minimum element of the heap. More...
 
Key getMinKey () const
 Returns the key of the minimum element of the heap. More...
 
void insert (Type elem, Key key)
 Inserts an item with a key into the heap. More...
 
int number () const
 Returns the number of elements in the heap. More...
 
void realloc (int newSize)
 Changes the size of the heap. More...
 
int size () const
 Returns the maximal number of elements which can be stored in the heap. More...
 

Private Member Functions

int father (int i) const
 Returns the index of the father of element i. More...
 
void heapify (int i)
 Is the central function to maintain the heap property. More...
 
int leftSon (int i) const
 Returns the index of the left son of node i. More...
 
int rightSon (int i) const
 Returns the index of the right son of node i. More...
 

Private Attributes

Array< Type > heap_
 
Array< Key > keys_
 
int n_
 

Friends

std::ostream & operator<< (std::ostream &out, const AbaBHeap< Type, Key > &heap)
 The output operator. More...
 

Detailed Description

template<class Type, class Key>
class abacus::AbaBHeap< Type, Key >

Binary heaps.

A heap is the representation of a binary tree by an array a.

The root of the tree is associated with a[0]. If a node corresponds to a[i], then its left son corresponds to a[2*i+1] and its right son to a[2*i+2]. This implicit binary tree is completely filled except possibly its highest level. Every item in the heap has to fulfil the heap property, i.e., its key has to be less than or equal than the keys of both sons.

This template class implements a heap with a fixed maximal size, however a reallocation can be performed if required.

The operations insert(), extractMin() require O(log n) running time if n elements are contained in the heap. The operation getMin() can even be executed in constant time. A heap can also be constructed from an ArrayBuffer of n elements which requires a running time of O(n) only.

The order of the elements in the heap is given by keys which are inserted together with each element of the heap. The class Key must be from an ordered type. Given two objects k1 and k2 of type Key then k1 has higher priority if the expression k1 < k2 holds.

Definition at line 38 of file bheap.h.

Constructor & Destructor Documentation

◆ AbaBHeap() [1/2]

template<class Type , class Key >
abacus::AbaBHeap< Type, Key >::AbaBHeap ( int  size)
explicit

A constructor.

Parameters
sizeThe maximal number of elements which can be stored.

◆ AbaBHeap() [2/2]

template<class Type , class Key >
abacus::AbaBHeap< Type, Key >::AbaBHeap ( const ArrayBuffer< Type > &  elems,
const ArrayBuffer< Key > &  keys 
)

A constructor with initialization.

The heap is initialized from an ArrayBuffer of elements and a corresponding ArrayBuffer of keys. The running time is O(n) for n elements.

Parameters
elemsA ArrayBuffer wich contains the elements.
keysA ArrayBuffer wich contains the keys.

Member Function Documentation

◆ check()

template<class Type , class Key >
void abacus::AbaBHeap< Type, Key >::check ( ) const

Throws an exception if the heap properties are violated.

This function is used for debugging this class.

◆ clear()

template<class Type , class Key >
void abacus::AbaBHeap< Type, Key >::clear ( )

Empties the heap.

◆ empty()

template<class Type , class Key >
bool abacus::AbaBHeap< Type, Key >::empty ( ) const

Return true if there are no elements in the heap, false otherwise.

◆ extractMin()

template<class Type , class Key >
Type abacus::AbaBHeap< Type, Key >::extractMin ( )

Accesses and removes the minimum element from the heap.

The minimum element is stored in the root of the tree, i.e., in heap_[0]. If the heap does not become empty by removing the minimal element, we move the last element stored in heap_ to the root (heap_[0]). Whereas this operation can destroy the heap property, the two subtrees rooted at nodes 1 and 2 still satisfy the heap property. Hence calling heapify(0) will restore the overall heap property.

Returns
The minimum element of the heap.

◆ father()

template<class Type , class Key >
int abacus::AbaBHeap< Type, Key >::father ( int  i) const
private

Returns the index of the father of element i.

◆ getMin()

template<class Type , class Key >
Type abacus::AbaBHeap< Type, Key >::getMin ( ) const

Returns the minimum element of the heap.

This operation must not be performed if the heap is empty. Since the heap property holds the element having minimal key is always stored in heap_[0].

◆ getMinKey()

template<class Type , class Key >
Key abacus::AbaBHeap< Type, Key >::getMinKey ( ) const

Returns the key of the minimum element of the heap.

This operation must not be performed if the heap is empty. Since the heap property holds the element having minimal key is always stored in heap_[0] and its key in key_[0].

◆ heapify()

template<class Type , class Key >
void abacus::AbaBHeap< Type, Key >::heapify ( int  i)
private

Is the central function to maintain the heap property.

The function assumes that the two trees rooted at left(i) and right(i) fulfil already the heap property and restores the heap property of the (sub-) tree rooted at i.

◆ insert()

template<class Type , class Key >
void abacus::AbaBHeap< Type, Key >::insert ( Type  elem,
Key  key 
)

Inserts an item with a key into the heap.

It is a fatal error to perform this operation if the heap is full.

Parameters
elemThe element being inserted into the heap.
keyThe key of this element.

◆ leftSon()

template<class Type , class Key >
int abacus::AbaBHeap< Type, Key >::leftSon ( int  i) const
private

Returns the index of the left son of node i.

◆ number()

template<class Type , class Key >
int abacus::AbaBHeap< Type, Key >::number ( ) const

Returns the number of elements in the heap.

◆ realloc()

template<class Type , class Key >
void abacus::AbaBHeap< Type, Key >::realloc ( int  newSize)

Changes the size of the heap.

Parameters
newSizeThe new maximal number of elements in the heap.

◆ rightSon()

template<class Type , class Key >
int abacus::AbaBHeap< Type, Key >::rightSon ( int  i) const
private

Returns the index of the right son of node i.

◆ size()

template<class Type , class Key >
int abacus::AbaBHeap< Type, Key >::size ( ) const

Returns the maximal number of elements which can be stored in the heap.

Friends And Related Function Documentation

◆ operator<<

template<class Type , class Key >
std::ostream& operator<< ( std::ostream &  out,
const AbaBHeap< Type, Key > &  heap 
)
friend

The output operator.

Writes the elements of the heap together with their keys on an output stream.

Parameters
outThe output stream.
heapThe heap being output.
Returns
A reference to the output stream.

Member Data Documentation

◆ heap_

template<class Type , class Key >
Array<Type> abacus::AbaBHeap< Type, Key >::heap_
private

Definition at line 189 of file bheap.h.

◆ keys_

template<class Type , class Key >
Array<Key> abacus::AbaBHeap< Type, Key >::keys_
private

Definition at line 190 of file bheap.h.

◆ n_

template<class Type , class Key >
int abacus::AbaBHeap< Type, Key >::n_
private

Definition at line 191 of file bheap.h.


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