Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::DeletingTop10Heap< X, Priority, STATICCOMPARER, INDEX > Class Template Reference

A variant of Top10Heap which deletes the elements that get rejected from the heap. More...

#include <ogdf/basic/MinHeap.h>

+ Inheritance diagram for ogdf::DeletingTop10Heap< X, Priority, STATICCOMPARER, INDEX >:

Public Member Functions

 DeletingTop10Heap (int size)
 Construct a DeletingTop10Heap of given maximal capacity. More...
 
void insertAndDelete (X *x, Priority p)
 Alternative name for pushAndDelete(). More...
 
void insertAndDeleteNoRedundancy (X *x, Priority p)
 Alternative name for pushAndKillNoRedundancy(). More...
 
void pushAndDelete (X *x, Priority p)
 Inserts the element x into the heap with priority p and deletes the element with smallest priority if the heap is full. More...
 
void pushAndDeleteNoRedundancy (X *x, Priority p)
 Analogous to pushandDelete(), but furthermore rejects (and deletes) an element if an equal element is already in the heap. More...
 
- Public Member Functions inherited from ogdf::Top10Heap< Prioritized< X *, double >, int >
 Top10Heap ()
 Constructor generating a heap which holds the 10 elements with highest value ever added to the heap. More...
 
bool full () const
 Returns true if the heap is completely filled (i.e. the next push operation will return something) More...
 
PushResult insert (Prioritized< X *, double > &x, Prioritized< X *, double > &out)
 Alternative name for push(). More...
 
void insertBlind (Prioritized< X *, double > &x)
 Alternative name for pushBlind(). More...
 
const Prioritized< X *, double > & operator[] (int idx) const
 obtain const references to the element at index idx More...
 
PushResult push (Prioritized< X *, double > &x, Prioritized< X *, double > &out)
 Tries to push the element x onto the heap (and may return a removed element as out). More...
 
void pushBlind (Prioritized< X *, double > &x)
 Simple (and slightly faster) variant of Top10Heap::push. More...
 

Additional Inherited Members

- Public Types inherited from ogdf::Top10Heap< Prioritized< X *, double >, int >
enum  PushResult
 The type for results of a Top10Heap::push operation. More...
 
- Static Public Member Functions inherited from ogdf::Top10Heap< Prioritized< X *, double >, int >
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. More...
 
static bool successful (PushResult r)
 Convenience function: Returns true if the PushResults states that the newly pushed element is new in the heap. More...
 
- Protected Member Functions inherited from ogdf::BinaryHeapSimple< Prioritized< X *, double >, int >
int 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 (int idx)
 
 BinaryHeapSimple (int 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...
 
Prioritized< X *, double > extractMin ()
 Returns the top (i.e., smallest) element and removed it from the heap [Same as pop(), O(log n)]. More...
 
const Prioritized< X *, double > & 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 (Prioritized< X *, double > &x)
 Adds an element to the heap [Same as push(), O(log n)]. More...
 
const Prioritized< X *, double > & operator[] (int idx) const
 obtain const references to the element at index idx (the smallest array index is 0, as for traditional C-arrays) More...
 
Prioritized< X *, double > pop ()
 Returns the top (i.e., smallest) element and removed it from the heap [Same as extractMin(), O(log n)]. More...
 
void push (Prioritized< X *, double > &x)
 Adds an element to the heap [Same as insert(), O(log n)]. More...
 
int size () const
 Returns the number of elements in the heap. More...
 
const Prioritized< X *, double > & 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...
 

Detailed Description

template<class X, class Priority = double, class STATICCOMPARER = StdComparer<X>, class INDEX = int>
class ogdf::DeletingTop10Heap< X, Priority, STATICCOMPARER, INDEX >

A variant of Top10Heap which deletes the elements that get rejected from the heap.

The datastructure of course requires the stored data-elements to be pointers (in order to be deletable when rejected). Hence the template parameter only specifies the data-type, without stating axplicitly that we considere pointers to the structure.

The datastructure also allows for non-duplicate insertions, i.e., a new element can be rejected if it is already in the heap. Note that only the compare function has to work

Definition at line 243 of file MinHeap.h.

Constructor & Destructor Documentation

◆ DeletingTop10Heap()

template<class X , class Priority = double, class STATICCOMPARER = StdComparer<X>, class INDEX = int>
ogdf::DeletingTop10Heap< X, Priority, STATICCOMPARER, INDEX >::DeletingTop10Heap ( int  size)
inlineexplicit

Construct a DeletingTop10Heap of given maximal capacity.

Definition at line 246 of file MinHeap.h.

Member Function Documentation

◆ insertAndDelete()

template<class X , class Priority = double, class STATICCOMPARER = StdComparer<X>, class INDEX = int>
void ogdf::DeletingTop10Heap< X, Priority, STATICCOMPARER, INDEX >::insertAndDelete ( X *  x,
Priority  p 
)
inline

Alternative name for pushAndDelete().

Definition at line 260 of file MinHeap.h.

◆ insertAndDeleteNoRedundancy()

template<class X , class Priority = double, class STATICCOMPARER = StdComparer<X>, class INDEX = int>
void ogdf::DeletingTop10Heap< X, Priority, STATICCOMPARER, INDEX >::insertAndDeleteNoRedundancy ( X *  x,
Priority  p 
)
inline

Alternative name for pushAndKillNoRedundancy().

Definition at line 283 of file MinHeap.h.

◆ pushAndDelete()

template<class X , class Priority = double, class STATICCOMPARER = StdComparer<X>, class INDEX = int>
void ogdf::DeletingTop10Heap< X, Priority, STATICCOMPARER, INDEX >::pushAndDelete ( X *  x,
Priority  p 
)
inline

Inserts the element x into the heap with priority p and deletes the element with smallest priority if the heap is full.

Like the Top10Heap, this function pushes the element x onto the heap with priority p, and extracts the element with smallest priority if the heap was already full. In contrast to the Top10Heap, this element which leaves the heap (or x itself if its priority was below all the priorities in the heap) gets deleted, i.e., removed from memory.

Definition at line 253 of file MinHeap.h.

◆ pushAndDeleteNoRedundancy()

template<class X , class Priority = double, class STATICCOMPARER = StdComparer<X>, class INDEX = int>
void ogdf::DeletingTop10Heap< X, Priority, STATICCOMPARER, INDEX >::pushAndDeleteNoRedundancy ( X *  x,
Priority  p 
)
inline

Analogous to pushandDelete(), but furthermore rejects (and deletes) an element if an equal element is already in the heap.

This function takes linear time in the worst case, and uses the compare function of the specified COMP template paremeter class, which can be any function returning true if two objects should be considered equal, and false otherwise.

Definition at line 268 of file MinHeap.h.


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