MinHeap implementation.

Description:  The below program is an implementation of MinHeap. While creating the MinHeap, youneed to specify the max. no of elements it can hold. It provides two operations insert() and getMinimum().


HeaderFile:

#include <exception>

using namespace std;

#define HEAP_EMPTY 1

#define HEAP_FULL 2

class MinHeapException : public exception
{
    private:
    int code;

    public:
    MinHeapException(int n) : code(n)
    {

    }

    const char* what() const throw()
    {
        switch(code)
        {
            case HEAP_EMPTY:
                return "Heap is empty.";

            case HEAP_FULL:
                return "Heap is full.";
        }
    }   
};


class MinHeap
{
    private:
   
    const int capacity;
    int size;
    int* ptr;

    public:

    MinHeap(int n);
       
    void insert(int n) throw(MinHeapException);

    int getMinimum() throw(MinHeapException);

    void display();

    ~MinHeap();   
};

Implementation of our MinHeap:

#include "MinHeap.h"
#include <iostream>

using namespace std;

MinHeap :: MinHeap(int n) : capacity(n), size(0), ptr(new int[n+1])
{
       
}


void MinHeap :: insert(int n) throw(MinHeapException)
{
    /*
     * If the heap is already full, throw a exception.
     */   
    if(size == capacity)
    {
        throw MinHeapException(HEAP_FULL);
    }

    int hole;

    /*Increment the size of heap*/
    size++;

     /*The hole points  to the last position.
     *Move up the hole, still we get suitable position. i.e the parent of the hole
     *must be greater than the new no. that we want to insert in the hole.
     */    for(hole = size ; hole > 1 && ptr[hole/2] > n; hole = hole/2)
    {
        ptr[hole] = ptr[hole/2];
    }

    ptr[hole] = n;
}


int MinHeap :: getMinimum() throw(MinHeapException)
{

    /*
     *If the heap is empty throw an exception.
     */        if(0 == size)
    {
        throw MinHeapException(HEAP_EMPTY);   
    }

    int firstelement = ptr[1];

    int lastelement = ptr[size];

    int hole;
    int smallelement;

    /*
     * Decrement the size of heap.
     */
    size--;

    /*
     * Intially the hole is created in the first element.
     * The hole is moved down till we get to a poistion where the childrens are greater than the last element.
     */      for(hole = 1;  hole <= size/2; hole = smallelement)
    {
       
        if(2*hole+1 <= size)
        {
            /*Ther are two childs*/
            if(lastelement < ptr[2*hole] && lastelement < ptr[2*hole+1])
            {
                /*Bot the children are greater than the lastelement. So last element can be placed here*/                break;
            }
           
            /*Find to which subtree the hole should be moved*/
            smallelement = ptr[2*hole] < ptr[2*hole+1] ? 2*hole : 2*hole+1;

        }
        else
        {       
            /*There is one child*/
            if(lastelement < ptr[2*hole])
            {
                /*The child is greater than the lastelement*/
                break;
            }
            smallelement = 2*hole;
        }

        /*Move the samllest children into hole. hole is moved done to smallest children  posistion*/            ptr[hole] = ptr[smallelement];   
    }
   
    /*Replace the hole with the last element*/
    ptr[hole] = lastelement;

    /*Return the first element*/
    return firstelement;

}

void MinHeap :: display()
{
    int i;

    for(i=1; i <= size; i++)
    {
        cout << ptr[i] << " ";
    }
    cout << endl;   
}

MinHeap :: ~MinHeap()
{
    delete [] ptr;
}


int main(int argc, char** argv)
{

    try
    {

            MinHeap heap(11);

            heap.insert(13);
            heap.insert(14);
            heap.insert(16);
            heap.insert(19);
            heap.insert(21);
            heap.insert(19);
            heap.insert(68);
            heap.insert(65);
            heap.insert(26);
            heap.insert(32);
            heap.insert(31);
            heap.insert(41);

            cout << "1st Minimum:" << heap.getMinimum() << endl;

            heap.display();

            cout << "2nd Minimum:" << heap.getMinimum() << endl;

            heap.display();

            cout << "3rd Minimum:" << heap.getMinimum() << endl;

            heap.display();

            cout << "4th Minimum:" << heap.getMinimum() << endl;

            heap.display();

            cout << "5th Minimum:" << heap.getMinimum() << endl;
    }
    catch(MinHeapException& e)
    {
        cout << e.what();
    }
}