public class Heapsort
{
	// Notkun: heapifyUp(f);
	// Fyrir:  Ekkert
	// Eftir:  f er hrúga með stærsta stak efst
	public static void heapifyUp(String[] f)
	{
		int n = f.length;
		int k = 0;

		while (k < n)
		{
			// f[0..k-1] uppfyllir hrúguskilyrði,
			// 0 <= k <=n
			rollup(f, 0, k, k);
			k++;
		}
	}

	// Notkun: rollup(f,i,j,k);
	// Fyrir:  f[i..j-1] er hrúga nema e.t.v.
	//         er f[k] of neðarlega
	// Eftir:  f[i..j-1] er hrúga
	static void rollup(String[] f, int i, int j, int k)
	{
		while (k > i)
		{
			// f[i..j-1] er í hrúgu nema e.t.v.
			// er f[k] of neðarlega.

			int parent = (k-1)/2;

			if (f[parent].compareTo(f[k]) >= 0)
				break;

			// f[k] > f[parent], þ.e. barn er stærra
			// en foreldri og þurfum því að víxla þeim

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

	// Notkun: heapifyDown(f);
	// Fyrir:  Ekkert
	// Eftir:  f er hrúga með stærsta stak efst
	public static void heapifyDown(String[] f)
	{
		int n = f.length;
		int k = n/2 - 1;

		while (k >= 0)
		{
			// f[k+1..n-1] uppfyllir hrúguskilyrði,
			// 0<=k<=n
			rolldown(f, k, n, k);
			k--;
		}
	}

	static void hsort(String[] f)
	{
		heapifyDown(f);

		// f[0..n-1] er hrúga

		int n = f.length;
		int k = n;
		while (k > 0)
		{
			// f[0..k-1] uppfyllir hrúguskilyrði og 
			// inniheldur minnstu stök f[0..n-1].
			// f[k..n-1] er í vaxandi röð og 
			// inniheldur stærstu stök f[0..n-1].
			// 0 <= k <= n
			k--;
			swap(f, 0, k);
			rolldown(f, 0, k, 0);
		}
	}

	// Notkun: rolldown(f,i,j,k);
	// Fyrir:  f[i..j-1] er hrúga nema e.t.v.
	//         er f[k] of ofarlega
	// Eftir:  f[i..j-1] er hrúga
	static void rolldown(String[] f, int i, int j, int k)
	{
		while (true)
		{
			// f[i..j-1] er hrúga nema e.t.v.
			// er f[k] of ofarlega
			// i <= k <= j

			int b = 2*k+1;

			if (b >= j) return;
			if (b+1 < j && f[b+1].compareTo(f[b]) > 0)
				b++;

			if (f[k].compareTo(f[b]) >= 0) return;

			swap(f, k, b);
			k = b;
		}
	}

	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)
	{
		String[] t = {"F","B","D","C","A","H"};

		hsort(t);

		for (int i = 0; i < t.length; i++)
			System.out.println(t[i]);
	}
}