I present here a
canonical implementation of a
generic binary heap algorithm. It has the
advantage of being
simple yet
fully featured. It can be used with items
comprised of
complicated classes or
simple intrinsic types.
A brief description of the algorithm is that the items are stored in a binary tree and the tree is a partial order of the items. We maintain the order whenever we insert or remove something from the tree. As a desirable consequence, the top most item (in the root of the tree) is always the minimum (or maximum) value of all the items in the tree.
By default, the T::operator < (with its traditional meaning of less than) is used to create a minimum heap but by reversing the meaning of T::operator < to actual mean greater than, you can create a maximum heap. If you do this, please comment it carefully and fully otherwise some poor sucker is going to be hopelessly confused when he comes along and tries to modify your code.
Binary heap algorithms have O(log n) execution for insertion and removal of an item where n is the size of the heap.
You can use a binary heap for sorting: it's called a heapsort surprisingly enough.
This code has been compiled and tested using MS VC++ 6.0 and DJGPP 3.04.
You can download this code from http://www.cjkware.com/wamckee/heap.zip
//
// The template class BinaryHeap uses the following functions:
//
// T::T ();
// T::~T ();
// T & T::operator = (const T & rhs);
// bool T::operator < (const T & rhs) const;
//
template <class T>
class BinaryHeap
{
public :
// Default constructor is always a good thing.
BinaryHeap ();
// Copy constructor, destructor and operator = required due to the
// deep structure of the heap (extra storage must be allocated and
// freed properly)
BinaryHeap (const BinaryHeap<T> & other);
~BinaryHeap ();
BinaryHeap<T> & operator = (const BinaryHeap<T> & other);
// Public interface for doing operation on the heap
void empty (); // remove all items from the heap
void insert (const T & item); // add a new item into the heap
void remove (); // remove the top item from the heap
const T & top () const; // get the top item from the heap
int size () const; // count how many items are in the heap
bool isEmpty () const; // true when there are no more items in the heap
private :
// Helper member functions
enum { DEFAULT_ALLOCATION_SIZE = 16 };
bool isFull () const; // true when we have run out of storage
void resize (); // logrithmically allocates more memory for the heap
T * storage; // where the heap is actually stored
int limit; // maximum number of items allowed in the heap
int count; // current number of items in the heap
void copy (T * thisData, T * otherData, int size); // moves item around
};
template <class T>
BinaryHeap<T>::BinaryHeap ()
{
empty ();
limit = 0;
// allocate default storage for the heap
storage = new T [DEFAULT_ALLOCATION_SIZE];
limit = DEFAULT_ALLOCATION_SIZE;
}
template <class T>
BinaryHeap<T>::BinaryHeap (const BinaryHeap<T> & other)
{
empty ();
limit = 0;
// allocate a new heap based on an old heap
storage = new T [other.limit];
count = other.count;
limit = other.limit;
// copy the old heap into the new heap
copy (storage, other.storage, count);
}
template <class T>
BinaryHeap<T>::~BinaryHeap ()
{
// recover previously allocated storage
delete [] storage;
}
template <class T>
BinaryHeap<T> & BinaryHeap<T>::operator = (const BinaryHeap<T> & other)
{
// recover the storage of the old heap
delete [] storage;
empty ();
limit = 0;
// allocate a new heap based on another heap
storage = new T [other.limit];
limit = other.limit;
count = other.count;
// make a copy of the heap
copy (storage, other.storage, count);
}
template <class T>
void BinaryHeap<T>::empty ()
{
// trivial and obvious
count = 0;
}
template <class T>
void BinaryHeap<T>::insert (const T & item)
{
// check to see if we need to make the storage bigger
if (isFull ()) resize ();
// start with the new item in the last most leaf of the heap
storage [count++] = item;
// start the bottom up sorting of the items
T * heap = storage;
int root = 0;
int bottom = count - 1;
// while we are not at the top (root) keep going
while (bottom > root)
{
// find the parent of the current item
int parent = (bottom - 1) / 2;
// if the item is less than it's parent, swap them
if (heap [bottom] < heap [parent])
{
T temp = heap [bottom];
heap [bottom] = heap [parent];
heap [parent] = temp;
// move up the binary tree one node and try again
bottom = parent;
}
else
{
// otherwise we stop
break;
}
}
}
template <class T>
void BinaryHeap<T>::remove ()
{
// move the last item in the tree to the top (thus deleting the top most item)
storage [0] = storage [--count];
// now move from the top down the item just placed in the top (root)
T * heap = storage;
int top = 0;
int size = count;
// while the left child of the current node is in the tree, we keep going
int leftChild = 2 * top + 1;
while (leftChild < size)
{
// get the right child and compute which (left or right) child is smaller (min)
int rightChild = 2 * top + 2;
int minChild = leftChild;
if ((rightChild < size) && (heap [rightChild] < heap [leftChild]))
minChild = rightChild;
// if the smaller child is less than the current node, we swap them
if (heap [minChild] < heap [top])
{
T temp = heap [top];
heap [top] = heap [minChild];
heap [minChild] = temp;
}
// now we move down the tree along the smallest child branch
top = minChild;
// compute the new left child for new current node in the tree
leftChild = 2 * top + 1;
// and try again
}
}
template <class T>
const T & BinaryHeap<T>::top () const
{
// trivial and obvious
return storage [0];
}
template <class T>
int BinaryHeap<T>::size () const
{
// trivial and obvious
return count;
}
template <class T>
bool BinaryHeap<T>::isFull () const
{
// trivial and obvious
return count == limit;
}
template <class T>
bool BinaryHeap<T>::isEmpty () const
{
// trivial and obvious
return count == 0;
}
template <class T>
void BinaryHeap<T>::resize ()
{
// logrithmic allocation: compute new size for storage of heap
limit = (limit <= 0) ? DEFAULT_ALLOCATION_SIZE : limit * 2;
// allocate storage
T * temp = new T [limit];
// copy old heap to new heap
copy (temp, storage, count);
// recover old heap
delete [] storage;
// point to new heap
storage = temp;
}
template <class T>
void BinaryHeap<T>::copy (T * thisData, T * otherData, int size)
{
// trivial and obvious
for (int i = 0; i < size; i++)
thisData [i] = otherData [i];
}
// sample program
class simple
{
public :
int data;
simple (int v) { data = v; }
private :
// required member functions
friend class BinaryHeap<simple>;
simple () { data = 0; }
bool operator < (const simple & rhs) const
{
return data < rhs.data;
}
};
#include <iostream>
int main ()
{
BinaryHeap<simple> bh;
int i;
// put 20 rand integers into the heap
for (i = 0; i < 20; i++)
{
simple x (rand ());
bh.insert (x);
std::cout << x.data << " ";
}
std::cout << std::endl;
// get all the integer back out (they should now be in decending order)
while (! bh.isEmpty ())
{
std::cout << bh.top ().data << " ";
bh.remove ();
}
std::cout << std::endl;
// we can also do this:
Binaryheap<int> int_heap;
int_heap.insert (100);
int data = int_heap.top ();
int_heap.remove ();
std::cout << data << std::endl;
return 0;
}