#include "minHeap.h"

// Paramaterized minHeap constructor that takes a vector 
// Should build the heap from bottom-up
minHeap::minHeap(vector<int> data) {

    // Set the contents of the heap vector to the input data vector
    heap = data;
    
    // Loop backwards through values in data vector
    for (int pos = data.size() - 1; pos >= 0; pos--) {

        // siftDown from pos
        siftDown(pos);

    }

}

// Return current position's parent node position
int parent(int pos) {

    return (floor((pos - 1) / 2));

}

// Return current position's left child node position
int leftChild(int pos) {

    return ((2 * pos) + 1);

}

// Return current position's right child node position
int rightChild(int pos) {

    return ((2 * pos) + 2);

}

// Repeatedly swap element A[i] with its parent 
// as long as A[i] violates the heap property with respect to 
// its parent (i.e., as long as A[i] < A[parent(i)]).
void minHeap::siftUp(int pos) {

    // If the parent node's position is within range of the heap vector
    if (parent(pos) < heap.size() - 1) {

        // If the value at the current node is less than the value at 
        // the current node's parent node, swap the values and siftUp 
        // from the parent node's position
        if (heap.at(pos) < heap.at(parent(pos))) {

            swap(heap.at(pos), heap.at(parent(pos)));

            siftUp(parent(pos));

        }

    }

}

// As long as A[i] violates the heap property  
// with one of its children, swap A[i] with its smallest child.
void minHeap::siftDown(int pos) {

    // Set the smallestChild position to the current position for comparisons
    int smallestChild = pos;

    // If the left child node's position is within range of the heap vector
    if (leftChild(pos) < heap.size()) {

        // If the value at the smallest child node is less than the value at 
        // the current node's left child node, set the smallest child position 
        // to the position of the left child node
        if (heap.at(smallestChild) > heap.at(leftChild(pos))) {

            smallestChild = leftChild(pos);

        }

    }

    // If the right child node's position is within range of the heap vector
    if (rightChild(pos) < heap.size()) {

        // If the value at the smallest child node is less than the value at 
        // the current node's right child node, set the smallest child position 
        // to the position of the right child node
        if (heap.at(smallestChild) > heap.at(rightChild(pos))) {

            smallestChild = rightChild(pos);

        }

    }

    // If the smallest child position has changed (not still the starting node), 
    // swap the values of the starting node and the smallest child node then 
    // siftDown from the smallest child node's position
    if (smallestChild != pos) {

        swap(heap.at(pos), heap.at(smallestChild));

        siftDown(smallestChild);

    }

}

// Insert value into heap
void minHeap::insert(int value) {

    // Place new element at the back of the heap
    heap.push_back(value);

    // siftUp from the back of the heap
    siftUp(heap.size() - 1);

}

// Removes minimum value
int minHeap::removeMin() {

    // Store value being removed
    int removed = heap.at(0);
    
    // Swap the first and last values in the heap
    swap(heap.at(0), heap.at(heap.size() - 1));

    // Remove the value at the back of the heap
    heap.pop_back();

    // siftDown from the front of the heap
    siftDown(0);

    // Return the removed value
    return removed;

}