package blatt10;

import java.util.Arrays;

public class Heapsort {
	
	/* Indizes im Array dargestellt im binären Heap-Baum:
	 * 
	 *                0
	 *              /   \
	 *             1     2
	 *            / \   /
	 *           3   4 5
	 */

	private int[] elements;
	
	public Heapsort(int[] elements) {
		this.elements = elements;
	}
	
	/** Gibt den Index des linken Nachfolgers des Elements am Index <index> zurück. */
	private int indexLeft(int index) {
		return index*2 + 1;
	}

	/** Gibt den Index des rechten Nachfolgers des Elements am Index <index> zurück. */
	private int indexRight(int index) {
		return index*2 + 2;
	}
	
	/** Vertauscht das Element am Index <index1> mit dem am Index <index2>. */
	private void swap(int index1, int index2) {
		int tmp = elements[index1];
		elements[index1] = elements[index2];
		elements[index2] = tmp;
	}
	
	/** Nimmt drei Indizes und gibt den Index des Minimums zurück. */
	private int getIndexOfMin(int index1, int index2, int index3) {
		// ArrayIndexOutOfBounds beachten!
		if (index1 < elements.length) {
			if (index2 < elements.length && elements[index2] < elements[index1]) {
				if (index3 < elements.length && elements[index3] < elements[index2])
					return index3;
				return index2;
			} else if (index3 < elements.length && elements[index3] < elements[index1])
				return index3;
			return index1;
		} else if (index2 < elements.length) {
			if (index3 < elements.length && elements[index3] < elements[index2])
				return index3;
			return index2;
		} else if (index3 < elements.length) {
			return index3;
		} else {
			return -1;
		}
	}
	
	/**
	 * Tauscht das Element am Index <index> mit dem linken oder rechten Nachfolger,
	 * wenn dieser kleiner ist (wenn beide kleiner sind, dann kleineres).
	 * Nach einem ggf. durchgeführten Tausch wird die Methode mit dem Index des
	 * vor dem Tausch kleineren Nachfolgers neu aufgerufen.
	 * 
	 * @param index  der Index des aktuell zu prüfenden Elements
	 * @param stop   der Index des letzten zu prüfenden Elements (nicht nötig)
	 */
	public void down(int index, int stop) {
		int minimumIndex = getIndexOfMin(index, indexLeft(index), indexRight(index));
		if (minimumIndex > index) {
			swap(index, minimumIndex);
			down(minimumIndex, stop);
		}
	}
	
	/** Wandelt das Array <elements> in einen korrekten binären Heap um. */
	public void buildHeap() {
		for (int i = (elements.length-1)/3; i >= 0; i--)
			down(i, elements.length-1);
	}
	
	/** Entfernt das oberste Elemente (die Wurzel) und gibt es zurück.
	 * Stellt die Invariante wieder her, indem die gelöschte Wurzel durch
	 * das letzte Element ersetzt wird (anschließend buildHeap).  */
	public int getMin() {
		int min = elements[0];
		swap(0, elements.length-1);
		elements = Arrays.copyOf(elements, elements.length-1); // letztes Element entfernen
		buildHeap();
		return min;
	}
	
	/** Sortiert das als Parameter übergebene Array mittels Heapsort. */
	public static int[] sort(int[] array) {
		Heapsort heap = new Heapsort(array);
		heap.buildHeap();
		int[] sorted = new int[array.length];
	    for (int i = 0; i < array.length; i++) {
	    	sorted[i] = heap.getMin();
	    }
	    return sorted;
	}
	
	public static void main(String[] args) {
		final int TEST_CASES = 1000;
		final int MAX_HEAP_SIZE = 1000;
		
		for (int i = 0; i < TEST_CASES; i++) {
			int[] array = new int[7];//(int)((MAX_HEAP_SIZE+1) * Math.random())];
			for (int j = 0; j < array.length; j++)
				array[j] = (int) (MAX_HEAP_SIZE * Math.random() / 2);
			int[] array2 = Arrays.copyOf(array, array.length);
			int[] array3 = Arrays.copyOf(array, array.length);
			
			array2 = sort(array2);
			Arrays.sort(array3);
			
			if (!Arrays.equals(array3, array2)) {
				System.out.println("Falsche Sortierung für Eingabe " + Arrays.toString(array));
				System.out.println("- sollte sein: " + Arrays.toString(array3));
				System.out.println("- war jedoch:  " + Arrays.toString(array2));
				break;
			}
		}
	}
}