A binary heap is a complete binary tree where every node has a key more extreme (greater or less) than or equal to the key of its parent. An array implementation stores the keys in an array. The parent of a node is the node's index in the array, divided by two, rounded down. Merging two binary heaps is O(n): the best you can do is just concatenate two heap arrays and make a heap of the result. Two binomial heaps can be merged in O(ln n).

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.

//
// 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;
}