Heap

package Lab07;

import java.io.*;

/*
 * Parent Node = (k-1)/2
 * Left Child = 2k + 1, Right Child = 2k + 2
 *
 * !!Need to write HeapSort!!  Is this needed?
 * !!Heap Order Property!! - Checked
 * !!Pop needs to return a Process!! - DONE
 *
 *  @Author Ryan DePrekel
 */

public class PriorityHeap {

    private Process[] queue;
    private int start_size = 16;
    private int size;

    /*
     ************************************************
     * Constructors to create PriorityHeap Object
     *   --Default: sets array length to start_size
     *   --int s:   sets array length to s
     ************************************************
     */
    public PriorityHeap(){
        size = 0;
        queue = new Process[start_size];
    }
    public PriorityHeap(int s){
        size = 0;
        queue = new Process[s];
    }

    public void print(){
        int i;
        for(i = 0; i < size; i++){
            System.out.println(i + " " + queue[i].getPriority());
        }
    }
    /*
     ************************************************
     * Push(): adds x to queue
     *         Adjusts size and calls walkUp(int pos)
     ************************************************
     */
    public void push(Process x){
        queue[size] = x;
        size++;
        walkUp(size - 1);
    }

    /*
     ************************************************
     * Pop() - Removes the head off the heap
     *         Adjusts size and calls walkDown(int pos)
     *        !!Needs to return a Process!!
     ************************************************
     */
    public Process pop() throws IOException{
        Process head = queue[0];
        queue[0] = queue[size - 1];
        size--;
        walkDown(0);
        return head;
    }

    /*
     * ***********************************************
     *                     Heap Sort
     * ***********************************************
     */
    /*public void sort(Process[] a){
        int i;
        queue = a;
        buildHeap();
        for(i = size;)
    }*/

    //Swaps based on position
    public void swap(int i, int j){
        Process temp = queue[i];
        queue[i] = queue[j];
        queue[j] = temp;
    }

    /*
     ************************************************
     *            --PRIVATE METHODS--
     ************************************************
     */

    // Returns true if queue is empty
    private boolean isEmpty(){
        return (size == 0);
    }

    // Returns left child's index
    private int getLeftChildIndex(int nodeIndex) {
        return 2 * nodeIndex + 1;
    }
    // Return right child's index
    private int getRightChildIndex(int nodeIndex) {
        return 2 * nodeIndex + 2;
    }
    // Returns parent's index
    private int getParentIndex(int nodeIndex) {
        if(nodeIndex == 0){
            return 0;
        }
        else
            return (nodeIndex - 1) / 2;
    }

    private void buildHeap(){
        size = queue.length - 1;
        for(int i = size/2; i > 0; i--)
            walkDown(i);
    }

    //Takes an element at position pos and walks it up the queue
    // to maintain heap order upon insertion of an element
    private void walkUp(int pos){
        Process temp = queue[pos];
        while((pos > 0) && temp.getPriority() < queue[getParentIndex(pos)].getPriority()){
            queue[pos] = queue[getParentIndex(pos)];
            pos = (pos - 1)/ 2;
        }
        queue[pos] = temp;
    }

    //Takes an element and position pos and walks it down the queue
    // to maintain heap order upon removal of an element
    private void walkDown(int pos){
        int sc = indexOfSmallest(pos);
        Process temp = queue[pos];
        while(getLeftChildIndex(pos) <= (size - 1) && temp.getPriority() > queue[sc].getPriority()){
            queue[pos] = queue[sc];
            pos = sc;
            sc = indexOfSmallest(pos);
        }
        queue[pos] = temp;
    }

    // Returns smallest child from parent at pos
    private int indexOfSmallest(int pos){
        int lc = getLeftChildIndex(pos);
        int rc = getRightChildIndex(pos);
        if(rc > (size - 1) || queue[lc].getPriority() < queue[rc].getPriority())
            return lc;
        else
            return rc;
    }

}