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) {
		// TODO
	}

	/** Gibt den Index des rechten Nachfolgers des Elements am Index <index> zurück. */
	private int indexRight(int index) {
		// TODO
	}
	
	/** Vertauscht das Element am Index <index1> mit dem am Index <index2>. */
	private void swap(int index1, int index2) {
		// TODO
	}
	
	/** Nimmt drei Indizes und gibt den Index des Minimums zurück. */
	private int getIndexOfMin(int index1, int index2, int index3) {
		// ArrayIndexOutOfBounds beachten!
		// TODO
	}
	
	/**
	 * 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) {
		// TODO
	}
	
	/** Wandelt das Array <elements> in einen korrekten binären Heap um. */
	public void buildHeap() {
		// TODO
	}
	
	/** 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() {
		// TODO
	}
	
	/** Sortiert das als Parameter übergebene Array mittels Heapsort. */
	public static int[] sort(int[] array) {
		// TODO
	}
	
	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;
			}
		}
	}
}