@@ -0,0 +1,1696 @@
+import java.util.Arrays;%0Aimport java.util.NoSuchElementException;%0A%0Apublic class MinHeap %7B%0A  private int%5B%5D arr;%0A  private int size;%0A%0A  public MinHeap(int capacity) %7B%0A    this.arr = new int%5Bcapacity%5D;%0A    this.size = 0;%0A  %7D%0A%0A  public MinHeap() %7B%0A    this(16);%0A  %7D%0A%0A  // True, if heap is empty%0A  public boolean isEmpty() %7B%0A    return size == 0;%0A  %7D%0A%0A  // Insert value into the heap%0A  public void insert(int elem) %7B%0A    if (size == arr.length) %7B%0A      resize();%0A    %7D%0A    arr%5Bsize%5D = elem;%0A    bubbleUp(size);%0A    ++size;%0A  %7D%0A%0A  // Peek min value%0A  public int min() %7B%0A    if (isEmpty()) throw new NoSuchElementException(%22Empty heap%22);%0A    return arr%5B0%5D;%0A  %7D%0A%0A  // Remove and return min value%0A  public int extractMin() %7B%0A    int min = min();%0A    --size;%0A    arr%5B0%5D = arr%5Bsize%5D;%0A    bubbleDown(0);%0A    return min;%0A  %7D%0A%0A  // == private methods ==%0A%0A  private void resize() %7B%0A    int%5B%5D tmp = new int%5Barr.length * 2%5D;%0A    System.arraycopy(arr, 0, tmp, 0, arr.length);%0A    arr = tmp;%0A  %7D%0A%0A  private void bubbleUp(int i) %7B%0A    while (i %3E 0) %7B%0A      int k = (i %25 2 == 0) ? (i - 2) / 2 : (i - 1) / 2;%0A      if (arr%5Bk%5D %3C= arr%5Bi%5D) break;%0A      swap(arr, k, i);%0A      i = k;%0A    %7D%0A  %7D%0A%0A  private void bubbleDown(int i) %7B%0A    while (i %3C size) %7B%0A      int l = i * 2 + 1, r = i * 2 + 2;%0A      if (r %3C size && arr%5Br%5D %3C arr%5Bl%5D) %7B%0A        l = r;%0A      %7D%0A      if (l %3C size && arr%5Bl%5D %3C arr%5Bi%5D) %7B%0A        swap(arr, l, i);%0A        i = l;%0A      %7D else %7B%0A        break;%0A      %7D%0A    %7D%0A  %7D%0A%0A  private static void swap(int%5B%5D arr, int a, int b) %7B%0A    int tmp = arr%5Ba%5D;%0A    arr%5Ba%5D = arr%5Bb%5D;%0A    arr%5Bb%5D = tmp;%0A  %7D%0A%0A  @Override%0A  public String toString() %7B%0A    return %22%7Bsize=%22 + size + %22, arr=%22 + Arrays.toString(arr) + %22%7D%22;%0A  %7D%0A%7D%0A

add min heap