import java.io.*;
import java.util.*;

public class Heap {
  public HeapNode root;

  public Heap () { root = null; }

  public boolean isEmpty () { return root == null; }

  public void insert (Comparable item) {
    root = HeapNode.insert (root, item);
  }

  public Comparable remove () {
    if (root == null) {
      System.out.println
	  ("error: tried to remove something from empty heap.");
      System.exit (-1);
    }
    Comparable result = root.item;
    root = HeapNode.reheapify (root);
    return result;
  }

  public void print () {
      // print the Heap in level order
    int height = HeapNode.height (root);

    for (int i = 0; i<height; i++) {
      HeapNode.printLevel (root, i, 0);
      System.out.println ("");
    }
  }
}

class HeapNode {
  public Comparable item;
  private HeapNode left, right;
  private int rank;

  public HeapNode (Comparable item, HeapNode left, HeapNode right) {
    this.item = item;
    this.left = left;
    this.right = right;
    this.rank = 1;
  }

  public static HeapNode insert (HeapNode node, Comparable item) {

    // to add a new element to a null HeapNode, just create a new object
    if (node == null) return new HeapNode (item, null, null);

    // call insert recursively on the appropriate child,
    // then check for the node property when the child returns.
    if (goLeft (node, item)) {
      node.left = insert (node.left, item);
      if (isBigger (node.left, node)) {
	swapContents (node, node.left);
      }
    } else {
      node.right = insert (node.right, item);
      if (isBigger (node.right, node)) {
	swapContents (node, node.right);
      }
    }
    setRank (node);
    return node;
  }

  public static HeapNode reheapify (HeapNode node) {
    // if there are no children, return an empty heap
    if (node.left == null && node.right == null) return null;

    // steal a item from the larger child and reheapify that child
    if (leftBigger (node)) {
      node.item = node.left.item;
      node.left = reheapify (node.left);
    } else {
      node.item = node.right.item;
      node.right = reheapify (node.right);
    }
    setRank (node);
    return node;
  }

  public static void printLevel (HeapNode node, int level, int sofar) {
    // level is the level we want to print.  sofar is what level of
    // the recursion we are on
    if (sofar == level) {
      if (node == null) {
	System.out.print ("n ");
      } else {
	System.out.print (node.item + " ");
      }

    } else if (node != null) {
      printLevel (node.left, level, sofar+1);
      printLevel (node.right, level, sofar+1);
    }
  }

  public static int height (HeapNode node) {
    if (node == null) return 0;
    int left = height (node.left) + 1;
    int right = height (node.right) + 1;
    if (left > right) return left;
    return right;
  }

    // PRIVATE METHODS

  private static boolean isBigger (HeapNode node1, HeapNode node2) {
    return node1.item.compareTo (node2.item) > 0;
  }

  private static boolean leftBigger (HeapNode node) {
    if (node.right == null) {
      return true;
    } else if (node.left == null) {
      return false;
    } else {
      return isBigger (node.left, node.right);
    }
  }

  private static boolean goLeft (HeapNode node, Comparable item) {
    if (node.left == null) {
      return true;
    } else if (node.right == null) {
      return false;
    } else {
      return (node.left.rank <= node.right.rank);
    }
  }

  private static void swapContents (HeapNode h1, HeapNode h2) {
    Comparable temp = h1.item;
    h1.item = h2.item;
    h2.item = temp;
  }

  private static void setRank (HeapNode node) {
    if (node.left == null || node.right == null) {
      node.rank = 0;
    } else {
      node.rank = Math.min (node.left.rank, node.right.rank) + 1;
    }
  }
}