/**
 * Implementacja sortowania przez kopcowanie.
 * www.algorytm.org
 * 
 * @author mephisto
 * 
 * @param <Key>
 *            typ klucza, rozszerza interfejs Comparable aby mozna go bylo
 *            swobodnie porownywac. Oczywiste, ze nalezaloby dodac jeszcze
 *            konstruktor, ktory przyjmuje Comparator, aby mozna bylo przekazac
 *            dowolny sposob porownywania
 */
public class HeapSort<Key extends Comparable<Key>> {

	public void sort(Key[] arr) {
		// tworzenie kopca
		int size = arr.length;
		for (int k = size / 2; k >= 1; k--) {
			sink(arr, k, size);
		}

		// sortowanie
		while (size > 1) {
			// celowo zamieniamy korzen z ostatnim elementem, aby potem go
			// zatopic i tym samym uzyskac najwiekszy element w indeksie 0
			exchange(arr, 1, size--);
			// zatapiamy korzen i przywracamy strukture kopca
			sink(arr, 1, size);
		}
	}

	/**
	 * 
	 * @param arr
	 * @return {@code true} jesli tablica jest posortowana, w przeciwnym razie
	 *         {@code false}
	 */
	public boolean isSorted(Key[] arr) {
		for (int i = 1; i < arr.length; i++)
			if (less(arr, i, i - 1))
				return false;
		return true;
	}

	// metoda do "zatapiania" elementu
	private void sink(Key[] arr, int k, int size) {
		// k jest indeksem rodzica
		while (2 * k <= size) {
			// indeks dziecka
			int j = 2 * k;
			// sprawdzamy, ktore z dzieci jest mniejsze
			if (j < size && less(arr, j, j + 1))
				j++;
			// sprawdzamy czy dziecko jest wieksze od rodzica
			if (!less(arr, k, j))
				break;
			// jest wieksze wiec zamieniamy
			exchange(arr, k, j);
			// zschodzimy poziom nizej w hierarchi kopca
			k = j;
		}
	}

	// zwraca true jesli element tablicy pod indeksem i jest mniejszy od
	// elementu pod indeksem j
	// celowo przeindeksowane o 1(metoda bedzie dostawac indeks wiekszy o jeden,
	// wtedy latwiej obliczac dzieci w kopcu)
	private boolean less(Key[] arr, int i, int j) {
		return arr[i - 1].compareTo(arr[j - 1]) < 0;
	}

	// zamienia miejscami dwa elementy w tablicy
	// celowo przeindeksowane o 1(metoda bedzie dostawac indeks wiekszy o jeden,
	// wtedy latwiej obliczac dzieci w kopcu)
	private void exchange(Key[] arr, int i, int j) {
		Key tmp = arr[i - 1];
		arr[i - 1] = arr[j - 1];
		arr[j - 1] = tmp;
	}

	/**
	 * Wypisuje cala tablice.
	 * 
	 * @param arr
	 *            tablica do wypisania
	 */
	public void printAll(Key[] arr) {
		for (Key it : arr) {
			System.out.print(it + " ");
		}
		System.out.println();
	}

	// klient testowy
	public static void main(String[] args) {
		Integer[] arr = new Integer[] { -4, 3, 4, 4, 111, -8 };
		HeapSort<Integer> instance = new HeapSort<Integer>();
		System.out.println("Przed sortowaniem: ");
		instance.printAll(arr);
		instance.sort(arr);
		System.out.println("Po sortowaniu: ");
		instance.printAll(arr);
	}
}