Heap (Winter 19 Exam)

import java.io.*;
import java.util.LinkedList;
import java.util.Scanner;
import java.lang.Math;
import java.lang.Integer;
import java.lang.String;

class Main {
    public static void main(String[] args) {
        // Uncomment the following two lines if you want to read from a file
        In.open("public/test3.in");
        Out.compareTo("public/test3.out");

      
        MaxHeap heap = new MaxHeap();
        //
        // Read the number of test cases, and start executing
        //
        int T = In.readInt();
        for (int test = 0; test < T; test += 1) {
          //
          // Read the command from the input
          //
          int command = In.readInt();
          if (command == 1) {
            //
            // If command is '1' then, we must read an array from the input
            // then, build a heap out of the array, using the 'buildHeap'
            // method, and finally, output the heap on the screen.        
            //
            heap.readHeap();
            heap.buildHeap();
            heap.writeHeap();
            
          } else if (command == 2) {
            //
            // if the command is set to '2', then we read the heap values,
            // which already have partial order that satisfies the heap
            // property. Then we read we insert M elements, reading the 
            // M number first.
            //
            heap.readHeap();        
            int M = In.readInt();
            for (int i = 0; i < M; i += 1) {          
              heap.insert(In.readInt());
            }        
            heap.writeHeap();
            
          } else if (command == 3) {
            //
            // if the command is set to '3', then we read the heap values,
            // which already have partial order that satisfies the heap
            // property. Then we delete the maximum elements M times, 
            // after reading the M number first.
            //
            heap.readHeap();        
            int M = In.readInt();;
            for (int i = 0; i < M; i += 1) {
              heap.deleteMax();
            }
            heap.writeHeap();
            
          }
        }
    
        // Uncomment the following line if you want to read from a file
        // In.close();
    }

   
}

class MaxHeap {
    //
    // We assume that the heap will not exceed MAX_HEAPSIZE length
    //
    final static int MAX_HEAPSIZE = 100000;    
    //
    // This field describes the number of elements that the heap holds
    //
    private int N = 0;
    //
    // The values of the heap are stored in this array
    //
    private int values[] = new int [MAX_HEAPSIZE];    
    //
    // Default empty constructor
    //
    public MaxHeap () { 
      // do nothing ...
    }    
    //
    // Helper function that provides comparison.
    //
    private boolean cmp(int a, int b) {
      return a < b;
    }
    //
    // Helper function that swaps the i-th & the j-th element of the heap
    //
    private void swap (int i, int j) {
      int tmp = values[i];
      values[i] = values[j];
      values[j] = tmp;
    }
    //
    // The heap will read the values. In this function, 
    // we assume that the values have partial order that satisfies the heap
    // condition.
    //
    public void readHeap () {      
      N = In.readInt();
      for (int i = 0; i < N; i += 1) {
        values[i] = In.readInt();
      }
    }
    //
    // Helper function that is used in printing the state of the heap.
    //
    public void writeHeap () {
      if (N > 0) {
        Out.print(values[0]);
        for (int i = 1; i < N; i += 1) {
          Out.print(" " + values[i]);
        }  
      }    
      Out.println();
    }    
  
    // ====================================================================================================================
    // Complete the methods below. Feel free to add additional methods / fields if needed.
    // ====================================================================================================================
  
    //
    // We assume that values are already stored in the values[] array, but they
    // do not hold the heap condition and have arbitrary order. We need to 
    // restore the heap condition using the method below.
    //
    public void buildHeap () {
      //
      // Your code goes here ...
      //
      int startIdx = (this.N / 2) - 1;
       //Out.println("Size of values is " + this.values.length);
      for (int i=startIdx;i>=0;i--){
        this.heapify(this.values, N, i);
      }
      
      /*//for each element in the array, swap it with its biggest child, stop before leaves
      for (int i=values.length-1;i>0;i--){
        int parentIndex;
        //if index of child is even, index of parent is minus 2 divided by 2
        if (i%2==0){
          parentIndex = (i-2)/2;
        }
        //if index of child is odd, index of parent is minus 1 divided by 2
        else{
          parentIndex = (i-1)/2;
        }
        //if parent is smaller than child
        if (values[parentIndex]<values[i]){
          //swap em
          this.swap(i,parentIndex);
        }
      }*/
    }
    
     static void heapify(int array[], int size, int i) 
  { 
    int largest = i;    // Initialize current node as largest 
    int left = 2 * i + 1;   // position of left child in array = 2*i + 1 
    int right = 2 * i + 2;   // position of right child in array = 2*i + 2 
                                             
    if (left < size && array[left] > array[largest])  // If left child is larger than root 
      largest = left; 
    
    if (right < size && array[right] > array[largest]) // If right child is larger than largest so far 
      largest = right; 
  
    if (largest != i) {         // If largest is not root swap it 
      int swap = array[i]; 
      array[i] = array[largest]; 
      array[largest] = swap; 
  
      heapify(array, size, largest); // Recursively heapify the sub-tree 
    } 
  } 
    
    //
    // Inserts a value in the heap, and places it on the right positions such
    // that the heap condition holds.
    //
    public void insert(int value) {             
      //
      // Your code goes here ...
      //
      
      //add to end of heap, call heapify on heap
      values[N] = value;
      siftUp(N);
      N++;
      /*int startIdx = (this.N / 2) - 1;
      for (int i=startIdx; i>=0; i--) {
        this.heapify(this.values, N, i);
      }
      */
    }
    
    public void siftUp(int i){
      int parentIndex;
        //if index of child is even, index of parent is minus 2 divided by 2
        if (i%2==0){
          parentIndex = (i-2)/2;
        }
        //if index of child is odd, index of parent is minus 1 divided by 2
        else{
          parentIndex = (i-1)/2;
        }
        //if parent is smaller than child
        if (i>0 && values[parentIndex]<values[i]){
          //swap em
          this.swap(i,parentIndex);
          siftUp(parentIndex);
        }
        
    }
    
    public void siftDownRoot(){
      heapify(this.values, this.N,0);
      
    }
    
    //
    // Pops the first value from the heap, restoring the heap condition
    //
    public void deleteMax () {        
      //
      // Your code goes here ...
      //
      values[0]=values[N-1];
      values[N-1]=0;
      N--;
      this.siftDownRoot();
    }    
    
    // ====================================================================================================================
    // End of implementation
    // ====================================================================================================================
}