// the heap is implemented as a binary tree embeded in an "array"
//    it is easy to direct access to a node using this relation:
//      left-child = parent * 2
//      right-child = (parent * 2) + 1
//    where parent, left-child, right-child
//    are indexes into the array

// assuming that the value of the node is "int"

// given an address of the node that needed to be adjusted
//    the adjustment is upward to the root
//    to restore the property of the heap

private void percolateUp( int hole ){
    int x = array[hole];
    while (hole > 1 && x < array[ hole/2 ] ){
        array[ hole ] = array[ hole/2 ];
        hole = hole/2;
    }
    array[ hole ] = x;
}


// given an address of the node that needed to be adjusted
//    the adjustment is downward to the leave
//    to restore the property of the heap

//    assume that "currentSize" is known

private void percolateDown( int hole ){
    int child;

    while( hole * 2 <= currentSize){
        child = hole * 2;
        if(child != currentSize && array[child+1] < array[child])
            child++;		// choose the smaller child
        if( array[child] < array[hole] )
            swap( hole, child );
        else
            break;
        hole = child;
    }
}

//  now the operation on the priority queue: insert, findMin, deleteMin

public void insert( int x ) throw Overflow {
    if( isFull( ) )	throw new Overflow( );
    currentSize++;
    array[currentSize] = x;
    percolateUp(currentSize);
}

public int findMin( ) {
    return array[ 1 ];
}

public int deleteMin( ) {
    int min = findMin( );
    currentSize--;
    array[ 1 ] = array[ currentSize];
    percolateDown( 1 );
    return min;
}

//  20 Nov 2009