import java.util.Comparator;

public class PriQueue<T>
{
	// Gildin í forgangsbiðröðinni eru í f[0..n-1]
	// í hrúgu með minnsta stak efst skv. cmp.
	//
	// Með öðrum orðum, þá gildir eftirfarandi
	// röð um hrúguna:
	//   cmp.compare(f[i], f[2*i+1]) < 0
	//   cmp.compare(f[i], f[2*i+2]) < 0
	private T[] f;
	private int n;
	private Comparator<T> cmp;

	// Notkun: pq = new PriQueue(max, cmp);
	// Fyrir:  max > 0
	// Eftir:  pq er ný tóm forgangsbiðröð með pláss fyrir
	//         max gildi. Gildið sem er fremst skv. cmp hefur
	//         hæstan forgang.
	@SuppressWarnings({"unchecked"})
	public PriQueue(int max, Comparator<T> cmp)
	{
		this.n = 0;
		this.f = (T[]) new Object[max];
		this.cmp = cmp;
	}

	// Notkun: s = pq.deleteMin();
	// Fyrir:  pq er ekki tóm.
	// Eftir:  s er minnsta gildið sem var í pq.
	//         s hefur verið fjarlægt úr pq.
	public T deleteMin()
	{
		T result = f[0];

		f[0] = f[--n];

		int i = 0;

		while (true)
		{
			// f[0..n-1] er hrúga nema e.t.v.
			// er f[i] of ofarlega.
			// 0 <= i <= n

			int b = 2*i+1;

			if (b >= n) return result; // f[i] er barnlaust (lauf)

			if (b+1 < n && cmp.compare(f[b+1], f[b]) < 0)
				// Veljum hægra barnið ef það er minna en vinstra
				b++;

			if (cmp.compare(f[i], f[b]) <= 0)
				// f[i] er á réttum stað
				return result;

			// f[b] < f[i], þ.e. foreldri er stærra
			// en barn og þurfum því að víxla þeim.

			swap(f, i, b);

			i = b;
		}
	}

	// Notkun: s = pq.peek();
	// Fyrir:  pq er ekki tóm.
	// Eftir:  s er minnsta gildið sem er í pq.
	public T peek()
	{
		return f[0];
	}

	// Notkun: pq.Put(s);
	// Fyrir:  pq er ekki full.
	// Eftir:  s hefur verið bætt við pq.
	public void Put(T s)
	{
		f[n++] = s;

		int i = n-1;

		while (i > 0)
		{
			// f[0..n-1] er í hrúgu nema e.t.v.
			// er f[i] of neðarlega.

			int parent = (i-1)/2;

			if (cmp.compare(f[parent], f[i]) <= 0)
				break;

			// f[i] < f[parent], þ.e. barn er minna
			// en foreldri og þurfum því að víxla þeim

			swap(f, i, parent);
			i = parent;
		}
	}

	// Notkun: n = pq.Count();
	// Eftir:  n er fjöldi staka í pq.
	public int Count()
	{
		return n;
	}

	// Notkun: b = pq.isFull();
	// Eftir:  b er satt þþaa. pq sé full.
	public boolean isFull()
	{
		return n == f.length;
	}

	private static <T> void swap(T[] f, int a, int b)
	{
		T tmp = f[a];
		f[a] = f[b];
		f[b] = tmp;
	}

	private static class AscendingOrder implements Comparator<String>
	{
		public int compare(String a, String b)
		{
			return a.compareTo(b);
		}
	}

	private static class DescendingOrder implements Comparator<String>
	{
		public int compare(String a, String b)
		{
			return b.compareTo(a);
		}
	}

	public static void main(String[] args)
	{
		PriQueue<String> pq = new PriQueue<String>(100, new AscendingOrder());
		//PriQueue<String> pq = new PriQueue<String>(100, new DescendingOrder());

		pq.Put("E");
		pq.Put("A");
		pq.Put("S");
		pq.Put("Y");
		pq.Put("Q");
		pq.Put("U");
		pq.Put("E");
		pq.Put("S");
		pq.Put("T");
		pq.Put("I");
		pq.Put("O");
		pq.Put("N");

		while (pq.Count() > 0)
			System.out.println(pq.deleteMin());
	}
}