// heappq.cpp - implements class HeapPQ (max size is 1000)
// cmc, 11/2/2013

#include "heappq.h"

HeapPQ::HeapPQ() : size(0) {
    array = new double[1001]; // will ignore array[0]
}

// put starts at end of array, then percolates up as needed
void HeapPQ::put(double value) {
    int position = ++size;
    int parent = position / 2;
    while (position > 1 && value > array[parent]) {
        array[position] = array[parent];
        position = parent;
        parent = position / 2;
    }
    array[position] = value;
}
 
// utility returns index of top child of position,
// or returns 0 if no children - used by get()
int HeapPQ::topChild(int position) {
    int child = position * 2; // left child
    if (child > size)
        return 0;
    if (child != size && array[child+1] > array[child])
        ++child; // change to right child
    return child;
}

// get returns top value, and replaces it with next top value
double HeapPQ::get() {
    double max = array[1];
    
    // consider last value for top position; move down as necessary
    double value = array[size--];
    int position = 1;
    if (size > 1) {
        int child = topChild(1);
        while (position * 2 <= size && array[child] > value) {
            array[position] = array[child];
            position = child;
            child = topChild(position);
        }
    }
    array[position] = value;
    return max;
}