import java.util.ArrayList;
import java.util.NoSuchElementException;

/* A MinHeap class of Comparable elements backed by an ArrayList. */
public class MinHeap<E extends Comparable<E>> {

    /* An ArrayList that stores the elements in this MinHeap. */
    private ArrayList<E> contents;
    private int size;
    // TODO: YOUR CODE HERE (no code should be needed here if not 
    // implementing the more optimized version)

    /* Initializes an empty MinHeap. */
    public MinHeap() {
        contents = new ArrayList<>();
        contents.add(null);
    }

    /* Returns the element at index INDEX, and null if it is out of bounds. */
    private E getElement(int index) {
        if (index >= contents.size()) {
            return null;
        } else {
            return contents.get(index);
        }
    }

    /* Sets the element at index INDEX to ELEMENT. If the ArrayList is not big
       enough, add elements until it is the right size. */
    private void setElement(int index, E element) {
        while (index >= contents.size()) {
            contents.add(null);
        }
        contents.set(index, element);
    }

    /* Swaps the elements at the two indices. */
    private void swap(int index1, int index2) {
        E element1 = getElement(index1);
        E element2 = getElement(index2);
        setElement(index2, element1);
        setElement(index1, element2);
    }

    /* Prints out the underlying heap sideways. Use for debugging. */
    @Override
    public String toString() {
        return toStringHelper(1, "");
    }

    /* Recursive helper method for toString. */
    private String toStringHelper(int index, String soFar) {
        if (getElement(index) == null) {
            return "";
        } else {
            String toReturn = "";
            int rightChild = getRightOf(index);
            toReturn += toStringHelper(rightChild, "        " + soFar);
            if (getElement(rightChild) != null) {
                toReturn += soFar + "    /";
            }
            toReturn += "\n" + soFar + getElement(index) + "\n";
            int leftChild = getLeftOf(index);
            if (getElement(leftChild) != null) {
                toReturn += soFar + "    \\";
            }
            toReturn += toStringHelper(leftChild, "        " + soFar);
            return toReturn;
        }
    }

    /* Returns the index of the left child of the element at index INDEX. */
    private int getLeftOf(int index) {
        // TODO: YOUR CODE HERE
        return 2 * index;
    }

    /* Returns the index of the right child of the element at index INDEX. */
    private int getRightOf(int index) {
        // TODO: YOUR CODE HERE
        return (2 * index) + 1;
    }

    /* Returns the index of the parent of the element at index INDEX. */
    private int getParentOf(int index) {
        // TODO: YOUR CODE HERE
        return index / 2;
    }

    /* Returns the index of the smaller element. At least one index has a
       non-null element. If the elements are equal, return either index. */
    private int min(int index1, int index2) {
        // TODO: YOUR CODE HERE
        if (index1 > size()) {
            return index2;
        }
        if (index2 > size()) {
            return index1;
        }
        int compared = contents.get(index1).compareTo(contents.get(index2));
        if (compared == 0) {
            return index1;
        } else if (compared < 1) {
            return index1;
        } else {
            return index2;
        }
    }

    /* Returns but does not remove the smallest element in the MinHeap. */
    public E findMin() {
        // TODO: YOUR CODE HERE
        return contents.get(1);
    }

    /* Bubbles up the element currently at index INDEX. */
    private void bubbleUp(int index) {
        // TODO: YOUR CODE HERE
        if (getParentOf(index) == 0) {
            return;
        }
        while (contents.get(index).compareTo(contents.get(getParentOf(index))) < 0) {
            int newIndex = getParentOf(index);
            swap(index, newIndex);
            index = newIndex;
            if (getParentOf(index) == 0) {
                return;
            }
        }
    }

    /* Bubbles down the element currently at index INDEX. */
    private void bubbleDown(int index) {
        // TODO: YOUR CODE HERE
        int smallest;
        if (getLeftOf(index) > size()) {
            return;
        } else if (getRightOf(index) > size()) {
            smallest = getLeftOf(index);
        } else {
            smallest = min(getLeftOf(index), getRightOf(index));
        }
        while (contents.get(index).compareTo(contents.get(smallest)) > 0) {
            E temp = contents.get(index);
            swap(index, smallest);
            index = smallest;
            if (getLeftOf(index) > size()) {
                return;
            } else if (getRightOf(index) > size()) {
                smallest = getLeftOf(index);
                continue;
            }
            smallest = min(getLeftOf(index), getRightOf(index));
        }
    }

    /* Returns the number of elements in the MinHeap. */
    public int size() {
        // TODO: YOUR CODE HERE
        int items = 0;
        for (int i = 0; i < contents.size(); i++) {
            if (contents.get(i) != null) {
                items += 1;
            }
        }
        return items;
    }

    /* Inserts ELEMENT into the MinHeap. If ELEMENT is already in the MinHeap,
       throw an IllegalArgumentException.*/
    public void insert(E element) {
        // TODO: YOUR CODE HERE
        if (contents.contains(element)) {
            throw new IllegalArgumentException("invalid argument");
        }
        setElement(size() + 1, element);
        bubbleUp(size());
    }

    /* Returns and removes the smallest element in the MinHeap. */
    public E removeMin() {
        // TODO: YOUR CODE HERE
        E item = contents.get(1);
        setElement(1, contents.get(size()));
        setElement(size(), null);
        bubbleDown(1);
        return item;
    }

    /* Replaces and updates the position of ELEMENT inside the MinHeap, which
       may have been mutated since the initial insert. If a copy of ELEMENT does
       not exist in the MinHeap, throw a NoSuchElementException. Item equality
       should be checked using .equals(), not ==. */
    public void update(E element) {
        // TODO: YOUR CODE HERE
        if (!contains(element)) {
            throw new NoSuchElementException("no such element");
        }
        for (int i = 1; i <=    size(); i++) {
            if (contents.get(i).equals(element)) {
                int compared = contents.get(i).compareTo(element);
                setElement(i, element);
                if (compared < 1) {
                    bubbleUp(i);
                } else if (compared > 1) {
                    bubbleDown(i);
                }
            }
        }
    }

    /* Returns true if ELEMENT is contained in the MinHeap. Item equality should
       be checked using .equals(), not ==. */
    public boolean contains(E element) {
        // TODO: YOUR CODE HERE
        for (int i = 1; i <= size(); i++) {
            if (contents.get(i).equals(element)) {
                return true;
            }
        }
        return false;
    }
    public ArrayList getContents() {
        return contents;
    }
}