[Java] Heapsort

public class Heap<E extends Comparable<E>> {

 private E[] a; // Array für Heap und Ergebnisliste
 int wurzel = 0; // Wurzelknoten des Heaps
 int lastHeap = -1; // letzter Knoten des Heaps

 // public Get-Methode fürs Array
 public E[] getA() {
 return a;
 }

 // Konstruktor 1 - erzeugt leeren Heap mit Länge len
 public Heap(int len) {
 a = (E[]) new Comparable[len];
 }

 // Konstruktor 2 - erzeugt Heap aus Parameter-Array
 public Heap(E[] b) {
 a = b;
 lastHeap = a.length-1;
 buildHeap();
 }

 // fügt Element ein und stellt Heapordnung wieder her
 public void insert(E e) {
 lastHeap++;
 a[lastHeap] = e;
 upHeap(lastHeap);
 }

 // verschiebt Element nach oben, bis Heapordnung hergestellt
 protected void upHeap(int i) {
 while (i > 0 && isGreaterThan(i, vater(i))) {
 swap(i, vater(i));
 i = vater(i);
 }
 }

 // stellt Heapordnung für kompletten Heapbaum her
 protected void buildHeap() {
 int k = (lastHeap-1)/2;
 while (k != -1) {
 heapify(k);
 k--;
 }
 }

 // stellt Heapordnung für Teilbaum mit Wurzel i her
 protected void heapify(int i) {
 while (i != -1)
 i = heapifyLocally(i);
 }

 // stellt Heapordnung für Knoten mit Wurzel i her
 protected int heapifyLocally(int i) {
 int m = maxKind(i);
 if (isGreaterThan(m, i)) {
 swap(m,i);
 return m;
 }
 else return -1; 
 }

 // entfernt das größte Element und stellt Heapordnung her
 public E extractMax() {
 E max = a[wurzel];
 a[wurzel] = a[lastHeap];
 lastHeap--;
 heapify(wurzel);
 return max;
 }

 // prüft ob Heap leer ist
 protected boolean heapEmpty() {
 return lastHeap == -1;
 }

 // liefert Index für linken Sohn
 protected int links(int i) {
 return 2*i + 1;
 }

 // liefert Index für rechten Sohn
 protected int rechts(int i) {
 return 2*i + 2;
 }

 // liefert Index für Vaterknoten
 protected int vater(int i) {
 return (i-1) / 2;
 }

 // liefert Index des größten Sohnknotens
 protected int maxKind(int i) {
 if (isGreaterThan(links(i), rechts(i)))
 return links(i);
 else if (isGreaterThan(rechts(i), links(i)))
 return rechts(i);
 else return i;
 }

 // prüft ob Knoten i größer ist als Knoten j
 protected boolean isGreaterThan(int i, int j) {
 if (i <= lastHeap && j <= lastHeap)
 return (a[j].compareTo(a[i]) < 0);
 else return false;
 }

 // vertauscht die Inhalte der Knoten i und j
 protected void swap(int i, int j) {
 E tmp = a[i];
 a[i] = a[j];
 a[j] = tmp;
 }

 // gibt gesamten Heapinhalt als String zurück
 public String toString() {
 StringBuffer s = new StringBuffer();
 for (int i = 0; i <= lastHeap; i++) {
 s.append(a[i].toString() + " ");
 }
 return "[ " + s + "]"; 
 }
}

public class HeapTest {
 
 public static void main (String[] args) {
 
 System.out.println("HEAP-TEST \n" +
 "---------------------\n");
 
 
 // Konstruktor 1 - INSERT
 Heap h1 = new Heap(10);
 for (int i = 1; i != 11; i++) {
 h1.insert(i);
 }
 System.out.println("Ausgabe Heap 1 - Insert");
 System.out.println(h1.toString());
 System.out.println();
 
 // Konstruktor 2 - BUILDHEAP
 Comparable[] c = {1,2,3,4,5,6,7,8,10,9};
 Heap h2 = new Heap(c);
 System.out.println("Ausgabe Heap 2 - BuildHeap");
 System.out.print(h2.toString());
 System.out.println("\n");
 
 // Konstruktor 1 - Extract Max 
 System.out.println("Heap 1 - ExtractMax");
 System.out.print("Heapgrösse: " + (h1.lastHeap+1) + " Elemente\n[ ");
 for (int i = 0; i < h1.getA().length; i++) {
 System.out.print(h1.extractMax() + " ");
 }
 System.out.println("]\n");
 
 // Konstruktor 2 - Extract Max
 System.out.println("Heap 2 - ExtractMax");
 System.out.print("Heapgrösse: " + (h2.lastHeap+1) + " Elemente\n[ ");
 for (int i = 0; i < h2.getA().length; i++) {
 System.out.print(h2.extractMax() + " ");
 }
 System.out.println("]\n");
 }
}