import java.util.*;

/** Abstract data type for a <tt>d</tt>-ary max-heap, to be implemented as a complete <tt>d</tt>-ary
  * tree using a Java array as the underlying storage.
  * The implementing class must offer a constructor that takes one argument, <tt>d</tt>,
  * which specifies the <em>arity</em> of the heap, i.e., the maximum number of children any one
  * node may have. If <tt>d</tt> is 2, then the instantiated object should be a 
  * <em>binary</em> heap; if <tt>d</tt> is 3, then the instantiated object should be a 
  * <em>ternary</em> heap; and so on. The arity <tt>d</tt> can yield different
  * time costs for the heap depending on how often (proportionally) nodes have to
  * "trickle down" and "bubbleUp" through the heap. If <tt>d</tt> is less than 2, then the
  * constructor should throw an <tt>IllegalArgumentException</tt>.
  * In addition, <tt>d</tt> will affect the height of a tree of any fixed number of elements.
  * @author Jacob Whitehill
  */
public interface Heap12<T extends Comparable<? super T>> {
	/** Removes all elements from the heap. */
	void clear ();

	/** Returns the number of elements currently stored in the
	  * heap.
	  * @return the number of elements stored in the heap.
	  */
	int size ();

	/** Returns (but does not remove) the largest element currently stored in the heap.
	  * Must take O(1) time (worst-case) for a heap of n elements.
	  * @throws NoSuchElementException if the heap is empty
	  * @return the largest element stored in the heap.
	  */
	T peekLargest ();

	/** Removes and returns the largest element currently stored in the heap.
	  * If the heap is empty, then this method throws a 
	  * <tt>NoSuchElementException</tt>.
	  * Must take O(log n) time (worst-case) for a heap of n elements.
	  * @throws NoSuchElementException if the heap is empty
	  * @return the largest element stored in the heap.
	  */
	T removeLargest ();

	/** If <tt>o</tt> is contained in the heap, then this method return the height of any arbitrary element
	  * of the heap that is equal to <tt>o</tt> (in the <tt>equals</tt> sense).
	  * Height is defined so that the root of the heap (i.e., the largest element) should have height
	  * 0; any child of the root should have height 1; any child of a child of the root should have height 2;
	  * and so on.
	  * @param o the element whose height is to be returned
	  * @throws NoSuchElementException
	  */
	int height (T o);

	/** If <tt>o</tt> is contained in the heap, then this method removes any arbitrary element
	  * of the heap that is equal to <tt>o</tt> (in the <tt>equals</tt> sense).
	  * If <tt>o</tt> is not contained in the heap, then the method throws a
	  * <tt>NoSuchElementException</tt>.
	  * May take O(n) time (worst-case) for a heap of n elements.
	  * @param o the element to remove
	  * @throws NoSuchElementException
	  */
	void remove (T o);

	/** Adds the specified element to the heap; <tt>o</tt> cannot be <tt>null</tt>.
	  * @param o the element to add.
	  */
	void add (T o);

	/** Returns whether or not the heap contains the specified element.
	  * May take O(n) time (worst-case) for a heap of n elements.
	  * @param o the element we wish to check
	  * @return whether <tt>o</tt> is stored in the heap.
	  */
	boolean contains (T o);

}