public class PriQueue
{
	// Gildin í forgangsbiðröðinni eru í f[0..n-1]
	// í hrúgu með stærsta stak efst
	private String[] f;
	private int n;

	// Notkun: pq = new PriQueue(max);
	// Fyrir:  max > 0
	// Eftir:  pq er ný tóm forgangsbiðröð með pláss fyrir
	//         max gildi
	public PriQueue(int max)
	{
		this.n = 0;
		this.f = new String[max];
	}

	// Notkun: s = pq.deleteMax();
	// Fyrir:  pq er ekki tóm.
	// Eftir:  s er eitt stærsta gildið sem var
	//         í pq. s hefur verið fjarlægt úr pq.
	public String deleteMax()
	{
		String 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 && f[b+1].compareTo(f[b]) > 0)
				// Veljum hægra barnið ef það er stærra en vinstra
				b++;

			if (f[i].compareTo(f[b]) >= 0)
				// f[i] er á réttum stað
				return result;

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

			swap(f, i, b);

			i = b;
		}
	}

	// Notkun: pq.Put(s);
	// Fyrir:  pq er ekki full.
	// Eftir:  s hefur verið bætt við pq.
	public void Put(String 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 (f[parent].compareTo(f[i]) >= 0)
				break;

			// f[i] > f[parent], þ.e. barn er stærra
			// 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 void swap(String[] f, int a, int b)
	{
		String tmp = f[a];
		f[a] = f[b];
		f[b] = tmp;
	}

	public static void main(String[] args)
	{
		PriQueue pq = new PriQueue(100);

		pq.Put("F");
		pq.Put("B");
		pq.Put("D");
		pq.Put("C");
		pq.Put("A");
		pq.Put("H");

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