#include <Heap.h>
Inheritance diagram for util::Heap< T, comparator >:
To obtain a sorted list out of a heap one may do something like this:
//Create a heap with an intial capacity of 100 elements. Heap<double,greater<double> > heap(100); //greater<double> isn't actually needed, it's the default //Fill the heap with 100 random numbers for (int i=0;i<100;i++) heap += drand48(); //Print out the elements in descending order. cerr << heap.removeElementAt(0) << " ";
Heap quarantees O(log(N)) complexity for insertion and deletion. The complexity for sorting N items, as in the previous example, is O(N*log(N)).
Note that if you use the insertElementAt method or alter the data directly, the order of the elements in the heap is undefined.
^{(1)} One may construct a reverse heap by supplying less<T> as the second template parameter. Please note that in this case sort() produces a list in descending order.
Public Methods  
Heap (int capacity=16, int blockSize=16)  
Create a heap with the given initial capacity and block size.  
Heap (const Heap &other)  
The copy constructor.  
void  addElement (const T &element) 
Add an element to the heap.  
T  removeElementAt (int index) 
Remove an element at the given index.  
void  sort () 
Sort the heap in place. 

Create a heap with the given initial capacity and block size.


Add an element to the heap. This method guarantees that the heap order is always preserved. Reimplemented from util::List< T >. 

Remove an element at the given index. The list will be heapified automatically. Reimplemented from util::List< T >. 

Sort the heap in place. After this method call, the elements in the list are in ascending order. Note that the heap does not have the heap property any more. (In fact it does have an inverse heap property.)
Note that the sort order can be changed by supplying different template parameters. The default, greater<T>, means that each parent in the tree is greater that its children. sort() sequentially removes the top of the tree and moves it to the end of the list. Therefore, by default, sort order is ascending. 