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.

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

Log in or register to write something here or to contact authors.