Implementieren Sie HeapSort für int-Werte. Verwenden Sie einen Min-Heap, so dass Ihre Klasse eine absteigende Sortierung realisiert.
Hinweis: Beachten Sie die Index-Verschiebung: In der Vorlesung lief der Index von Arrays ab 1, weshalb die Formeln (z.B. für Kindknoten) leicht angepasst werden müssen.
package de.hsrm.cs.ads;
public class HeapSort {
private int leftChild(int i) {
// FIXME: implement
}
private int rightChild(int i) {
// FIXME: implement
}
// Korrigiere einen inkorrekten Wert an Stelle i
// (siehe Vorlesung)
private void min_heapify(int[] a, int i) {
// FIXME: implement
}
// Verwandelt das Array in einen Heap
// (siehe Vorlesung)
private void build_min_heap(int[] a) {
heap_size = a.length;
for (int i = heap_size/2; i >= 0; --i) {
min_heapify(a, i);
}
}
// HeapSort
public void sort(int[] a) {
// FIXME: implement
}
}
Subato
