/***************************  HeapSort.java  **********************************/
import AlgoTools.IO;

/** Iteratives Sortieren mit Heapsort 
 *  Entnimm einem Heap so lange das kleinste Element, bis er leer ist.
 *  Die entnommenen Elemente werden im selben Array gespeichert.
 */

public class HeapSort {

  private static void sift (int[] a, int l, int r) { // repariere Array a   
                                               // in den Grenzen von l bis r 
    int i, j;                                  // Indizes
    int x;                                     // Array-Element
    i = l; x = a[l];                           // i und x initialisieren
    j = 2 * i + 1;                             // linker Sohn
    if ((j < r) && (a[j + 1] < a[j])) j++;     // jetzt ist j der kleinere Sohn
    while ((j <= r) && (a[j] < x)) {           // falls kleinerer Sohn existiert
        a[i] = a[j];
        i    = j; 
        j    = 2 * i + 1;
        if ((j < r) && (a[j + 1] < a[j])) j++; // jetzt ist j der kleinere Sohn
    }
    a[i] = x;
  }

  public static void sort (int[] a) {          // statische Methode sort 
    int l, r, n, tmp;                          // links, rechts, Anzahl, tmp
    n = a.length;                              // Zahl der Heap-Eintraege 
    for (l = (n - 2) / 2; l >= 0; l--)         // beginnend beim letzten Vater
        sift(a, l, n - 1);                     // jeweils Heap reparieren 
    for (r = n - 1; r > 0; r--) {              // rechte Grenze fallen lassen 
        tmp  = a[0];                           // kleinstes Element holen
        a[0] = a[r];                           // letztes nach vorne
        a[r] = tmp;                            // kleinstes nach hinten
        sift(a, 0, r-1);                       // Heap korrigieren
    } 
  }
}