import java.util.*;

public class MaxHeap {
  private ArrayList<Integer> data_;

  public MaxHeap() {
    data_ = new ArrayList<Integer>();
  }

  // Given an index, return the parent index
  private int parent(int index) {
    return (index - 1) / 2;
  }
  private int lchild(int index) {
    return (2* index + 1);
  }
  private int rchild(int index) {
    return (2* index + 2);
  }

  public void insert(int value) {
    this.data_.add(value);
    int index = data_.size() - 1;
    while (this.data_.get(index) > this.data_.get(parent(index))) {
      Collections.swap(this.data_, index, parent(index));
      index = parent(index);
    }
  }

  //////////////////////////////
  //ATTEMPT #1

  /*
  public void remove(int index) {
    //swap node to remove with the last node in the heapremove the last nodebubble down (“heapify”) to correct position
    int last = data_.size() - 1;
    if(index == last){
      data_.remove(last);
    }
    else{
      //swaps index wanted to be deleted with last element and then deletes last element
      Collections.swap(this.data_, index, last);
      data_.remove(last);
      boolean finding = true;

      while(!finding){
        int max = 0;
        if (data_.size()-1 >= data_.get(lchild(index)) && data_.size()-1 >= data_.get(rchild(index))){

          if(data_.get(lchild(index)) >= data_.get(rchild(index))){
            max = data_.get(lchild(index));
            Collections.swap(this.data_, index, lchild(index));
            index = lchild(index);
          }
          else if(data_.get(rchild(index)) > data_.get(lchild(index))){
            max = data_.get(rchild(index));
            Collections.swap(this.data_, index, rchild(index));
            index = rchild(index);
          }
        }
        else if(data_.size()-1 >= data_.get(lchild(index)) && data_.size()-1 < data_.get(rchild(index))){
          max = data_.get(lchild(index));
          Collections.swap(this.data_, index, lchild(index));
          index = lchild(index);
        }
        else if(data_.size()-1 < data_.get(lchild(index)) && data_.size()-1 >= data_.get(rchild(index))){
          max = data_.get(rchild(index));
          Collections.swap(this.data_, index, rchild(index));
          index = rchild(index);
        }
        else{
          finding = false;
          break;
        }
      }
    }
  }
  */

/////////////////////////////
//ATTEMPT #2

/*
public void remove(int index) {
    //swap node to remove with the last node in the heapremove the last nodebubble down (“heapify”) to correct position
    int last = data_.size() - 1;
    if(index == last){
      data_.remove(last);
    }
    else{
      //swaps index wanted to be deleted with last element and then deletes last element
      Collections.swap(this.data_, index, last);
      data_.remove(last);
      trickleDown(index);
    }
  }
  public void trickleDown(int index){
    // TASK: Check if leaf, if that's the case do nothing
    if (data_.size()-1 < data_.get(lchild(index)) && data_.size()-1 < data_.get(rchild(index)))
      return;

    // TASK: Initialize children variables
    int leftChildIndex  = index * 2;
    int rightChildIndex = (index * 2) + 1;
    int minChildIndex;

    // TASK: Check if rightChildren doesn't exist, in that case
    // the minChildIndex is the left, otherwise, find the min children
    if (rightChildIndex > data_.size()-1) {
      minChildIndex = leftChildIndex;
    }
    else {
      minChildIndex = (this.data_.get(leftChildIndex) < this.data_.get(rightChildIndex)) ? leftChildIndex : rightChildIndex;
    }

    // TASK: stop in case the parent is already smaller than the children
    if (this.data_.get(index) < this.data_.get(minChildIndex)) return;

    Collections.swap(this.data_, index, minChildIndex);

    // TASK: apply the same algorithm recursively
    trickleDown(minChildIndex);
  }
*/
///////////////////////


  public int extractMax() {
    throw new RuntimeException("Not implemented!");
  }

  public int getMax() {
    throw new RuntimeException("Not implemented!");
  }

  public void print() {
    for (Integer i : data_) {
      System.out.print(i + " ");
    }
      System.out.println();
  }

  public boolean isEmpty() {
    return data_.isEmpty();
  }
}