// Heap-Sort auf Strings
// sortiert zeilenweise von stdin oder einem angegebenen File nach stdout
//
// Klaus Kusche, 2002

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#define LINELEN 4096
#define MAXLINES 1000000

// *** Achtung: ***
// Ein Heap wird in einem Array traditionell ab Index 1 gespeichert
// (weil die Index-Rechnungen dann einfacher sind),
// Das Element [0] bleibt unbenutzt!!!

// heapsort verwendet einen Heap mit dem *größten* Element an der Wurzel!

// Hilfsfunktion zum Heap Erzeugen
// und zum Heap Wiederherstellen nach Entnahme eines Elementes:
// betrachte a[left]...a[right] als Teil eines Heaps a[1]...a[right]
// a[left+1]...a[right] stimmt schon,
// a[left] muß erst an die richtige Stelle "einsickern",
// alles links von a[left] ist egal
#ifdef SIMPLE_HEAPIFY
// schöne Variante
void heapify(const char *a[], int left, int right)
{
  int father, lson, rson;
  const char *tmp;

  father = left;
  // a[father]..."Vater", a[2*father] und a[2*father+1]..."Söhne"
  // tausche Vater mit größerem der beiden Söhne
  // bis Vater größer als beide Söhne ist oder kein Sohn mehr im Heap ist
  for (;;) {
    lson = 2 * father;
    rson = 2 * father + 1;
    if (lson > right)
      return;                          // kein Sohn mehr, fertig
    if ((rson <= right) && (strcoll(a[lson], a[rson]) < 0)) {
      // rechter Sohn ist vorhanden und größer als linker Sohn
      // vergleiche rechten Sohn mit dem Vater
      if (strcoll(a[father], a[rson]) >= 0)
        return;                        // Vater ist größer, fertig!
      tmp = a[father];                 // Sohn ist größer, mit Vater tauschen
      a[father] = a[rson];
      a[rson] = tmp;
      father = rson;                   // getauschten Sohn weiterprüfen
    } else {
      // linker Sohn ist größer: dasselbe mit linkem Sohn
      if (strcoll(a[father], a[lson]) >= 0)
        return;                        // Vater ist größer, fertig!
      tmp = a[father];                 // Sohn ist größer, mit Vater tauschen
      a[father] = a[lson];
      a[lson] = tmp;
      father = lson;                   // getauschten Sohn weiterprüfen
    }
  }
}
#else
// das gleiche, optimierte Version aus Wirth
void heapify(const char *a[], int left, int right)
{
  int father, son;
  const char *tmp;

  tmp = a[left];                       // einzusickerndes Element
  // a[father]..."Vater", a[2*father] und a[2*father+1]..."Söhne"
  // tausche Vater mit größerem der beiden Söhne
  // bis Vater größer als beide Söhne ist oder kein Sohn mehr im Heap ist
  for (father = left; (son = 2 * father) <= right; father = son) {
    // stelle son auf den größeren der beiden Söhne
    if (((son + 1) <= right) && (strcoll(a[son], a[son + 1]) < 0))
      ++son;
    // vergleiche diesen mit dem einzusickernden Element
    if (strcoll(tmp, a[son]) >= 0)
      break;                           // Vater ist größer, fertig!
    a[father] = a[son];                // Sohn ist größer, ersetzt Vater
  }
  a[father] = tmp;                     // Element gehört hierher
}
#endif

// sortiere a[1]...a[n]
void heapsort(const char *a[], int n)
{
  int i;
  const char *t;

  // erster Schritt: Verwandle unsortiertes Array in einen Heap
  // von der Mitte nach vor: Jedes Element einzeln einsickern
  for (i = n / 2; i >= 1; --i) {
    heapify(a, i, n);
  }

  // zweiter Schritt:
  // baue sortiertes Array elementweise von hinten nach vorne auf:
  // Entnimm größtes verbleibendes Element (Wurzel des Heap, a[1])
  // und tausche es mit dem nächsten Element am hinteren Ende
  // mach Heap 1 kürzer, lass nach vorne getauschtes Element einsickern
  // bis der Heap nur mehr 1 Element hat
  for (i = n; i > 1; --i) {
    t = a[i];
    a[i] = a[1];
    a[1] = t;
    heapify(a, 1, i - 1);
  }
}

int main(int argc, const char *argv[])
{
  const char *a[MAXLINES + 1];
  char line[LINELEN + 2];
  int i, n = 0;
  FILE *f;

  if (argc == 1) {
    f = stdin;
  } else if (argc == 2) {
    if ((f = fopen(argv[1], "r")) == NULL) {
      fprintf(stderr, "%s: error opening %s: %s\n", argv[0], argv[1],
              strerror(errno));
      exit(EXIT_FAILURE);
    }
  } else {
    fprintf(stderr, "Aufruf: %s [inputfile]\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  while (fgets(line, sizeof (line), f)) {
    ++n;
    if (!strchr(line, '\n')) {
      fprintf(stderr, "%s: Incomplete line %d\n", argv[0], n);
      exit(EXIT_FAILURE);
    }
    if (n > MAXLINES) {
      fprintf(stderr, "%s: Too many input lines: %d\n", argv[0], n);
      exit(EXIT_FAILURE);
    }
    a[n] = strdup(line);
    if (a[n] == NULL) {
      fprintf(stderr, "%s: Cannot store input line %d: %s\n", argv[0], n,
              strerror(errno));
      exit(EXIT_FAILURE);
    }
  }

  if (ferror(f)) {
    fprintf(stderr, "%s: Error reading %s: %s\n", argv[0],
            (argc == 1) ? "stdin" : argv[1], strerror(errno));
    exit(EXIT_FAILURE);
  }
  fclose(f);

  heapsort(a, n);

  for (i = 1; i <= n; ++i) {
    if (fputs(a[i], stdout) == EOF) {
      fprintf(stderr, "%s: Error writing stdout: %s\n", argv[0],
              strerror(errno));
      exit(EXIT_FAILURE);
    }
  }
  if (fclose(stdout) != 0) {
    fprintf(stderr, "%s: Error closing stdout: %s\n", argv[0], strerror(errno));
    exit(EXIT_FAILURE);
  }

  exit(EXIT_SUCCESS);
}