Developer Documentation
ACG::HeapT< HeapEntry, HeapInterface > Class Template Reference

#include <ACG/Utils/HeapT.hh>

Inheritance diagram for ACG::HeapT< HeapEntry, HeapInterface >:

Public Types

typedef std::vector< HeapEntry > Base

Public Member Functions

 HeapT ()
 HeapT (const HeapInterface &_interface)
 Construct with a given HeapIterface.
 ~HeapT ()
void clear ()
 clear the heap
bool empty ()
 is heap empty?
unsigned int size ()
 returns the size of heap
void reserve (unsigned int _n)
 reserve space for _n entries
void reset_heap_position (HeapEntry _h)
 reset heap position to -1 (not in heap)
bool is_stored (HeapEntry _h)
 is an entry in the heap?
void insert (HeapEntry _h)
 insert the entry _h
HeapEntry front ()
 get the first entry
void pop_front ()
 delete the first entry
void remove (HeapEntry _h)
 remove an entry
void update (HeapEntry _h)
bool check ()
 check heap condition

Private Types

typedef std::vector< HeapEntry > HeapVector

Private Member Functions

void upheap (unsigned int _idx)
 Upheap. Establish heap property.
void downheap (unsigned int _idx)
 Downheap. Establish heap property.
HeapEntry entry (unsigned int _idx)
 Get the entry at index _idx.
void entry (unsigned int _idx, HeapEntry _h)
 Set entry _h to index _idx and update _h's heap position.
unsigned int parent (unsigned int _i)
 Get parent's index.
unsigned int left (unsigned int _i)
 Get left child's index.
unsigned int right (unsigned int _i)
 Get right child's index.

Private Attributes

HeapInterface interface_
 Instance of HeapInterface.

Detailed Description

template<class HeapEntry, class HeapInterface = HeapEntry>
class ACG::HeapT< HeapEntry, HeapInterface >

An efficient, highly customizable heap.

The main difference (and performace boost) of this heap compared to e.g. the heap of the STL is that here to positions of the heap's elements are accessible from the elements themself. Therefore if one changes the priority of an element one does not have to remove and re-insert this element, but can just call the update(HeapEntry) method.

This heap class is parameterized by two template arguments:

  • the class HeapEntry, that will be stored in the heap
  • the HeapInterface telling the heap how to compare heap entries and how to store the heap positions in the heap entries.

Definition at line 121 of file HeapT.hh.

Member Function Documentation

template<class HeapEntry , class HeapInterface = HeapEntry>
void ACG::HeapT< HeapEntry, HeapInterface >::update ( HeapEntry  _h)

update an entry: change the key and update the position to reestablish the heap property.

Definition at line 204 of file HeapT.hh.

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