---

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

#include <Heap.h>

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

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.

• It is complete.
  • All leaf nodes reside in at most two adjacent levels.
  • It is filled from left.
• It has the heap property.
  • No child node in the tree is greater than its parent.⁽¹⁾

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.

⁽¹⁾ 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.

---

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:

• Heap.h

---

Documentation generated on 11.09.2003 with Doxygen.
The documentation is copyrighted material.
Copyright © Topi Mäenpää 2003. All rights reserved.