#include <stdio.h>

#define ARRAYLEN 11

void heapSort(int * a, const int len);
void sink(int * a, const int start, const int end);

// allgemeine Array-Werkzeuge
void copyArray(int * source, int * dest, const int len);
void printArray(const int * a, const int len);
void swap(int * a, int * b);

void heapSort(int * a, const int len)
{
  int i;
  for (i=len/2; i>=1; --i)
  {
    sink(a, i, len);
  }

  for (i=len; i>1; --i)
  {
    swap(&a[1], &a[i]);
    sink(a, 1, i-1);
  }
}

void sink(int * a, int k, const int end)
{
  int son;
  while(1)
  {
    if (2*k > end) return; // Der Knoten hat keinen Sohn.
    if (2*k+1 <= end) // Knoten hat sogar zwei Söhne
    {
      son = 2*k+1;
      if(a[son] < a[son-1]) --son; // Kleineren von beiden auswählen!
    }
    else
    {
      son = 2*k; // Nur ein Sohn - nur eine Möglichkeit!
    }

    if (a[k] < a[son])
    {
      swap(&a[k], &a[son]);
      k=son;
    }
    else  // Keine Vertauschung notwenig
    {
      break;
    }
  }

}

void copyArray(int * source, int * dest, const int len)
{
  int i;
  for (i=0; i<len; ++i)
  {
    dest[i] = source[i];
  }
}

void printArray(const int * a, const int len)
{
  int i;
  for (i=0; i<len; ++i)
  {
    printf(" %d", a[i]);
  }
  printf("\n");
}

void swap(int * a, int * b)
{
  if (a==b) return;
  *a ^= *b;
  *b ^= *a;
  *a ^= *b;
}

int main(void) {
  int unordnung[ARRAYLEN] = { 999, 4, 7, 2, 5, 1, 9, 3, 8, 6, 0 };

  // Das Array fängt mit 999 an, weil es einfach eine große Zahl ist, die
  // bei einem Fehler im Algorithmus nach hinten wandert, weil es keine größere
  // Zahl im Array gibt.

  printArray(unordnung, ARRAYLEN);
  heapSort(unordnung, ARRAYLEN-1);
  printArray(unordnung, ARRAYLEN);

  return 0;
}