Main Page   Class Hierarchy   Alphabetical List   Compound List   Compound Members  

util::Heap< T, comparator > Class Template Reference

#include <Heap.h>

Inheritance diagram for util::Heap< T, comparator >:

util::List< T > util::Iterator< T > util::Object List of all members.

Detailed Description

template<class T, class comparator = std::greater<T>>
class util::Heap< T, comparator >

Heap is an implementation of a binary tree with the properties listed below.

Elements can be added to a heap as they are added to any list using the += operator or the addElement method. The binary tree is stored as a list in breadth-first order.

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.

removeElementAt (int index)
 Remove an element at the given index.

void sort ()
 Sort the heap in place.


Constructor & Destructor Documentation

template<class T, class comparator = std::greater<T>>
util::Heap< T, comparator >::Heap int    capacity = 16,
int    blockSize = 16
[inline]
 

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

Parameters:
capacity  the number of elements this heap will hold without expanding.
blockSize  the amount of items to grow when expanding


Member Function Documentation

template<class T, class comparator>
void util::Heap< T, comparator >::addElement const T &    element [virtual]
 

Add an element to the heap.

This method guarantees that the heap order is always preserved.

Reimplemented from util::List< T >.

template<class T, class comparator>
T util::Heap< T, comparator >::removeElementAt int    index [virtual]
 

Remove an element at the given index.

The list will be heapified automatically.

Reimplemented from util::List< T >.

template<class T, class comparator>
void util::Heap< T, comparator >::sort  
 

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.


The documentation for this class was generated from the following file:
Documentation generated on 11.09.2003 with Doxygen.
The documentation is copyrighted material.
Copyright © Topi Mäenpää 2003. All rights reserved.