/***************************  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 das 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    = j*2+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
    } 
  }
}