Heap Sort

Heap Sort ist ein instabiler Sortieralgorithmus, der mit Heaps arbeitet.

Idee

1. Max-Heap aufbauen
   • Auf dem letzten Knoten (=Vorgänger vom letzten Blatt = ) wird Heapify aufgerufen, dann der davor usw.
2. Wurzel (größtes Element) mit letztem Element aus dem Heap tauschen
3. Heap ist jetzt um 1 Element kleiner, am Schluss stehen die sortierten Elemente
4. Wurzel mit Heapify einsickern lassen
5. Schritte 2-4 wiederholen bis Liste sortiert

Laufzeit

Asymptotisch optimal

Implementierung

heapSort(ArrayList<Integer> list) {
 
	// Heap aufbauen
	// Start beim letzten Knoten (= Vorgänger vom letzten Element(=size))
	for(int i = (list.size() - 2) / 2; i >= 0; i--) {
		heapify(list, i, list.size());
	}
 
	for(int i = list.size()-1; i > 0; i--) {
		swap(list, 0, i);
		heapify(list, 0, i-1);
	}
}
 
heapify(ArrayList<Integer> list, int element, int size) {
	int leftChild = 2 * element + 1;
	int rightChild = 2 * element + 2;
 
	// to be compared to sicker-element
	int child;
 
	// element hat nachfolger?
	if(!(leftChild <= size-1))
		return;
 
	// element hat 2. nachfolger?
	if(rightChild <= size-1) {
		// größeren nachfolger berechnen
		child = list.get(leftChild) > list.get(rightChild) ? leftChild : rightChild;
	}
	else {
		child = leftChild;
	}
 
	// element muss sickern?
	if(list.get(child) < list.get(element))
		return;
 
	swap(list, child, element);
 
	heapify(list, child, size-1);
}