public class Heap<E> {
  private java.util.ArrayList<E> list = new java.util.ArrayList<>();
  private java.util.Comparator<? super E> c;
  
  /** Tworzy domyślny kopiec */
  public Heap() {
    this.c = (e1, e2) -> ((Comparable<E>)e1).compareTo(e2);
  }

  /** Tworzy kopiec z podanym komparatorem */
  public Heap(java.util.Comparator<E> c) {
    this.c = c;
  }
  
  /** Tworzy kopiec na podstawie tablicy obiektów */
  public Heap(E[] objects) {
    this.c = (e1, e2) -> ((Comparable<E>)e1).compareTo(e2);
    for (int i = 0; i < objects.length; i++)
      add(objects[i]);
  }

  /** Dodawanie nowego obiektu do kopca */
  public void add(E newObject) {
    list.add(newObject); // Dołączanie obiektu do kopca
    int currentIndex = list.size() − 1; // Indeks ostatniego węzła

    while (currentIndex > 0) {
      int parentIndex = (currentIndex - 1) / 2;
      // Przestawianie, jeśli bieżący obiekt jest większy niż rodzic
      if (c.compare(list.get(currentIndex),
          list.get(parentIndex)) > 0) {
        E temp = list.get(currentIndex);
        list.set(currentIndex, list.get(parentIndex));
        list.set(parentIndex, temp);
      }
      else
        break; // Drzewo jest teraz kopcem

      currentIndex = parentIndex;
    }
  }

  /** Usuwanie korzenia z kopca */
  public E remove() {
    if (list.size() == 0) return null;

    E removedObject = list.get(0);
    list.set(0, list.get(list.size() - 1));
    list.remove(list.size() - 1);

    int currentIndex = 0;
    while (currentIndex < list.size()) {
      int leftChildIndex = 2 * currentIndex + 1;
      int rightChildIndex = 2 * currentIndex + 2;

      // Znajdowanie maksymalnego dziecka
      if (leftChildIndex >= list.size()) break; // Drzewo jest kopcem
      int maxIndex = leftChildIndex;
      if (rightChildIndex < list.size()) {
        if (c.compare(list.get(maxIndex),
            list.get(rightChildIndex)) < 0) {
          maxIndex = rightChildIndex;
        }
      }

      // Przestawianie, jeśli bieżący węzeł jest mniejszy od maksimum
      if (c.compare(list.get(currentIndex), 
      		list.get(maxIndex)) < 0) {
        E temp = list.get(maxIndex);
        list.set(maxIndex, list.get(currentIndex));
        list.set(currentIndex, temp);
        currentIndex = maxIndex;
      }
      else
        break; // Drzewo jest kopcem
    }

    return removedObject;
  }

  /** Pobieranie liczby węzłów w drzewie */
  public int getSize() {
    return list.size();
  }
  
  /** Zwraca true, jeśli kopiec jest pusty */
  public boolean isEmpty() {
    return list.size() == 0;
  }
}
