BinaryHeap

/*
 * BinaryHeap.cpp
 *
 *  Created on: 15 Eki 2011
 *      Author: Serdar KUZUCU
 */

#include <iostream>
#include <math.h>

using namespace std;

template<typename Comparable>
class BinaryHeap {
    public:
    explicit BinaryHeap( int capacity = 3 ) {
        objects = new Comparable[capacity+1];
        this->capacity = capacity;
        this->currentsize = 0;
    }

    void insert(const Comparable &o) {
        if(currentsize == capacity) {
            resize((capacity+1)*2);
        }
        int cell = ++currentsize;
        for(; cell>1 && objects[cell/2] > o; cell/=2)
            objects[cell] = objects[cell/2];
        objects[cell] = o;
    }

    void deleteMin() {
        objects[1] = objects[currentsize--];
        percolateDown(1);
    }

    void print() {
        int size = currentsize;
        int numsatir = 0;
        for(numsatir = 0; size>0; size-=pow(2,numsatir)+1, numsatir++);

        int citem = 1;
        for(int i=0; i<=numsatir; i++) {
            for(int k=numsatir-i; k>0; k--) {
                cout << " ";
            }

            for(int k=0; k<pow(2,i) && currentsize>=citem; k++) {
                cout << objects[citem++] << "  ";
            }
            cout << endl;
        }
        cout << endl;
    }

    bool empty() {
        return (currentsize==0);
    }

    private:
    int currentsize;
    int capacity;
    Comparable *objects;

    void resize(int newcapacity) {
        Comparable *newobjects = new Comparable[newcapacity];
        for(int i=0; i<=currentsize; i++) {
            newobjects[i] = objects[i];
        }
        delete(objects);
        this->objects = newobjects;
        capacity = newcapacity-1;
    }

    void percolateDown(int hole) {
        Comparable temp = objects[hole];
        int child;
        for( ; hole*2<=currentsize; hole = child ) {
            child = hole*2;
            if(child != currentsize && objects[child+1] < objects[child]) {
                child++;
            }
            if(objects[child] < temp) {
                objects[hole] = objects[child];
            } else {
                break;
            }
        }
        objects[hole] = temp;
    }
};