Heap.cpp

#include <iostream>

using namespace std;

template<class T> class PriorityQueue
{
    public:
        virtual T* extractMax() = 0;
        virtual PriorityQueue* enqueue(T* x) = 0;
        virtual int size() = 0;
};

template<class H> class BinaryHeap
{
    private:
        int length;
        int heapsize;
        H** A;

        int left(int i) { return i<<1; }
        int right(int i) { return (i<<1)|1; }
        int parent(int i) { return i>>1; }

        void swap(int i, int j)
        {
            H* temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }

        void heapify(int i)
        {
            if( i > heapsize ) return;
            int max = i;
            int l = left(i);
            int r = right(i);

            if( l < heapsize && compare(A[l], A[max]))
                max = l;
            if( r < heapsize && compare(A[r], A[max]))
                max = r;
            swap(i, max);
            heapify(max);
        }

    public:

        BinaryHeap(int size)
        {
            A = new H*[size];
            length = size;
            heapsize = 0;
        }

        virtual bool compare(H* x, H* y) = 0;

        H* extractMax()
        {
            if( heapsize == 0 ) return NULL;
            swap(1, heapsize);
            heapsize--;
            heapify(1);

            return A[heapsize+1];
        }

        BinaryHeap<H>* enqueue(H x)
        {
            heapsize++;
            A[heapsize] = new H(x);
            int i = heapsize;
            while( i > 1 && compare(A[i], A[parent(i)]))
            {
                swap(i, parent(i));
                i = parent(i);
            }
            return this;
        }

        int size()
        {
            return heapsize;
        }

        BinaryHeap<H>* increaseKey(int i, H* k)
        {
            if( i > heapsize ) return this;
            if( i < 1 ) return this;
            if( *A[i] > *k ) return this;

            *A[i] = *k;

            while( i > 1 && compare(A[i], A[parent(i)]))
            {
                swap(i, parent(i));
                i = parent(i);
            }
            return this;
        }

        void print()
        {
            cout << "HEAP: ";
            for( int i = 1; i <= heapsize; i++)
                cout << *A[i] << " ";
            cout << endl;
        }
};

template<class H> class MaxBinaryHeap : public BinaryHeap<H>
{
    public:
        bool compare( H* x, H* y) { return (*x > *y ? true : false); }

        MaxBinaryHeap(int size) : BinaryHeap<H>(size) {}
};

template<class H> class MinBinaryHeap : public BinaryHeap<H>
{
    public:
        bool compare( H* x, H* y) { return (*x < *y ? true : false); }

        MinBinaryHeap(int size) : BinaryHeap<H>(size) {}
};

int main()
{
    MinBinaryHeap<int>* B = new MinBinaryHeap<int>(100);
    B->enqueue(28)->enqueue(42)->enqueue(45)->enqueue(12)->enqueue(3)->enqueue(49)->enqueue(68)->enqueue(30)->enqueue(46);
    B->print();

    return 0;
}