# OpenGraph DrawingFramework

v.2012.07

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

A variant of BinaryHeapSimple which always holds only the X (e.g. X=10) elements with the highest keys. More...

#include <ogdf/basic/MinHeap.h>

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

List of all members.

## Public Types

enum  PushResult { Accepted, Rejected, Swapped }
The type for results of a Top10Heap::push operation. More...

## Public Member Functions

Top10Heap ()
Constructor generating a heap which holds the 10 elements with highest value ever added to the heap.
Top10Heap (INDEX size)
Constructor generating a heap which holds the size elements with highest value ever added to the heap.
INDEX capacity () const
Returns the size of the heap specified when constructing: this is the number of top elements stored.
void clear ()
empties the heap
bool empty () const
Returns true if the heap contains no elements.
bool full () const
Returns true if the heap is completely filled (i.e. the next push operation will return something)
PushResult insert (X &x, X &out)
Alternative name for push().
void insertBlind (X &x, X &out)
Alternative name for pushBlind().
const X & operator[] (INDEX idx) const
obtain const references to the element at index idx
PushResult push (X &x, X &out)
Tries to push the element x onto the heap (and may return a removed element as out).
void pushBlind (X &x)
Simple (and slightly faster) variant of Top10Heap::push.
INDEX size () const
Returns the number of elements in the heap.

## Static Public Member Functions

static bool returnedSomething (PushResult r)
Convenience function: Returns true if the PushResults states that push caused an element to be not/no-longer in the heap.
static bool successful (PushResult r)
Convenience function: Returns true if the PushResults states that the newly pushed element is new in the heap.

Protected Member Functions inherited from ogdf::BinaryHeapSimple< X, INDEX >
BinaryHeapSimple (INDEX size)
Construtor, giving initial array size.
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)].
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)].
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)].
void heapdown ()
void heapup (INDEX idx)

## Detailed Description

### template<class X, class INDEX = int> class ogdf::Top10Heap< X, INDEX >

A variant of BinaryHeapSimple which always holds only the X (e.g. X=10) elements with the highest keys.

It assumes that the data-elements are themselves comparable, i.e., the compare-function of the items implicitly defines the keys.

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

Definition at line 196 of file MinHeap.h.

## Member Enumeration Documentation

template<class X, class INDEX = int>

The type for results of a Top10Heap::push operation.

Enumerator:
 Accepted Rejected Swapped

Definition at line 199 of file MinHeap.h.

## Constructor & Destructor Documentation

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

Constructor generating a heap which holds the 10 elements with highest value ever added to the heap.

Definition at line 207 of file MinHeap.h.

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

Constructor generating a heap which holds the size elements with highest value ever added to the heap.

Definition at line 209 of file MinHeap.h.

## Member Function Documentation

template<class X, class INDEX = int>
 INDEX ogdf::Top10Heap< X, INDEX >::capacity ( ) const
inline

Returns the size of the heap specified when constructing: this is the number of top elements stored.

Reimplemented from ogdf::BinaryHeapSimple< X, INDEX >.

Definition at line 218 of file MinHeap.h.

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

empties the heap

Reimplemented from ogdf::BinaryHeapSimple< X, INDEX >.

Definition at line 221 of file MinHeap.h.

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

Returns true if the heap contains no elements.

Reimplemented from ogdf::BinaryHeapSimple< X, INDEX >.

Definition at line 212 of file MinHeap.h.

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

Returns true if the heap is completely filled (i.e. the next push operation will return something)

Definition at line 214 of file MinHeap.h.

template<class X, class INDEX = int>
 PushResult ogdf::Top10Heap< X, INDEX >::insert ( X & x, X & out )
inline

Alternative name for push().

Definition at line 254 of file MinHeap.h.

template<class X, class INDEX = int>
 void ogdf::Top10Heap< X, INDEX >::insertBlind ( X & x, X & out )
inline

Alternative name for pushBlind().

Definition at line 271 of file MinHeap.h.

template<class X, class INDEX = int>
 const X& ogdf::Top10Heap< 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. Useful, e.g., when iterating through the final heap elements.

Reimplemented from ogdf::BinaryHeapSimple< X, INDEX >.

Definition at line 280 of file MinHeap.h.

template<class X, class INDEX = int>
 PushResult ogdf::Top10Heap< X, INDEX >::push ( X & x, X & out )
inline

Tries to push the element x onto the heap (and may return a removed element as out).

If the heap is not yet completely filled, the pushed element is accepted and added to the heap. The function returns Accepted, and the out parameter is not touched.

If the heap is filled and the key of the pushed element is too small to be accepted (i.e. the heap is filled with all larger elements), then the element if rejected: The funtion returns Rejected, and the out parameter is set to x.

If the heap is filled and the key of the pushed element is large enough to belong to the top elements, the element is accepted and the currently smallest element in the heap is removed from the heap. The function returns Swapped and sets the out parameter to the element removed from the heap.

You may want to use the convenience funtions successful and returnedSomething on the return-value if you are only interested certain aspects of the push.

Definition at line 240 of file MinHeap.h.

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

Simple (and slightly faster) variant of Top10Heap::push.

The behavior is the identical to Top10Heap::push, but there is nothing reported to the outside

Definition at line 262 of file MinHeap.h.

template<class X, class INDEX = int>
 static bool ogdf::Top10Heap< X, INDEX >::returnedSomething ( PushResult r )
inlinestatic

Convenience function: Returns true if the PushResults states that push caused an element to be not/no-longer in the heap.

Definition at line 204 of file MinHeap.h.

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

Returns the number of elements in the heap.

Reimplemented from ogdf::BinaryHeapSimple< X, INDEX >.

Definition at line 216 of file MinHeap.h.

template<class X, class INDEX = int>
 static bool ogdf::Top10Heap< X, INDEX >::successful ( PushResult r )
inlinestatic

Convenience function: Returns true if the PushResults states that the newly pushed element is new in the heap.

Definition at line 202 of file MinHeap.h.

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