#ifndef HEAP_CPP
#define HEAP_CPP 1
#include "Heap.h"

/**
 * Construct the binary heap.
 * capacity is the capacity of the binary heap.
 */
//template <class TreeNode*>
Heap::Heap( int capacity )
{
    key  = new int[capacity+1];
    array = new TreeNode*[capacity + 1];
    currentSize=0;
    this->capacity = capacity;
}

/**
 * Insert item x with associated key into the heap, maintaining 
 * heap order. Duplicates are allowed.
 */
//template <class TreeNode*>
bool Heap::insert( int newKey, TreeNode* x )
{
    if( isFull( ) ) {
        cout << "Heap::insert - Heap is full." << endl;
        return false;
    }

    // Percolate up
    int hole = ++currentSize;
    for( ; hole > 1 && newKey < key[ hole / 2 ]; hole = hole/2 ){
        key[ hole ] = key[ hole / 2 ];
        array[ hole ] = array[ hole / 2 ];
    }
    key[ hole ] = newKey;
    array[ hole ] = x;
    return true;
}

/**
 * Find the smallest item in the heap.
 * Return the smallest item in 'minItem' and associated key as
 * return value of the function.
 */
//template <class TreeNode*>
int Heap::findMin(TreeNode*& minItem ) const
{
    if( !isEmpty( ) ) {
        minItem = array[ 1 ];
        return key[ 1 ];
    }
}
// Remove the smallest item and return it.
TreeNode* Heap::removeMin()
{
    TreeNode* node;
    deleteMin( node );
    return node;
}
/**
 * Remove the smallest item from the heap
 * and place it in minItem..
 */
//template <class TreeNode*>
int Heap::deleteMin( TreeNode*& minItem )
{
    int returnKey;
    if( !isEmpty( ) ) {
        minItem = array[1];
        returnKey = key[1];
        key[ 1 ] = key[ currentSize ];
        array[ 1 ] = array[ currentSize ];
        currentSize = currentSize - 1;
        percolateDown( 1 );
    }
    return returnKey;
}

/**
 * Establish heap order property from an arbitrary
 * arrangement of items. Runs in linear time.
 */
//template <class TreeNode*>
void Heap::buildHeap( )
{
    for( int i = currentSize / 2; i > 0; i-- )
        percolateDown( i );
}

/**
 * Test if the heap is logically empty.
 * Return true if empty, false otherwise.
 */
//template <class TreeNode*>
bool Heap::isEmpty( ) const
{
    return currentSize == 0;
}

/**
 * Test if the heap is logically full.
 * Return true if full, false otherwise.
 */
//template <class TreeNode*>
bool Heap::isFull( ) const
{
    return currentSize == capacity - 1;
}

/**
 * Make the heap logically empty.
 */
//template <class TreeNode*>
void Heap::makeEmpty( )
{
    currentSize = 0;
}

/**
 * Internal method to percolate down in the heap.
 * hole is the index at which the percolate begins.
 */
//template <class TreeNode*>
void Heap::percolateDown( int hole )
{
    int child;
    int tmp = key[ hole ];
    TreeNode* saveData = array[ hole ];

    for( ; hole * 2 <= currentSize; hole = child )
    {
        child = hole * 2;
        if( child != currentSize && key[child+1] < key[ child ] )
            child++;
        if( key[ child ] < tmp ) {
            key[ hole ] = key[ child ];
            array[ hole ] = array[ child ];
        }
        else
            break;
    }
    key[ hole ] = tmp;
    array[ hole ] = saveData;
}
#endif


