// Priority queue (mit kleinstem Element vorne)
//
// Aufruf: priqueue n1 n2 ...
//
// Klaus Kusche, 2019

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define SIZE 100

typedef struct {
  int cnt; // Anzahl der aktuell in arr enthaltenen Elemente
  // Element 0 bleibt immer unbenutzt,
  // sonst hätten wir in jeder Index-Rechnung ein zusätzliches +1 oder -1
  int arr[SIZE];
} priqueue;

bool put(priqueue *pq, int val);
bool get(priqueue *pq, int *val);

// speichert val in pq
// liefert true bei Erfolg, false wenn voll
bool put(priqueue *pq, int val)
{
  int i, j;

  if (pq->cnt >= SIZE - 1) return false;

  ++(pq->cnt);  // queue bekommt 1 Element mehr
  i = pq->cnt;  // i = Index des "Loches" für das neue Element
                // am Anfang: Erster freier Platz hinten im Array
                
  // solange das Loch einen Vater hat
  // und der Vater größer als der neue Wert ist:
  // Vater-Wert wandert nach hinten in das Loch,
  // Loch wandert nach vor in den Vater
  while (((j = i / 2) > 0) && (pq->arr[j] > val)) {
    pq->arr[i] = pq->arr[j];
    i = j;
  }
  pq->arr[i] = val;  // neuen Wert im Loch speichern

  return true;
}

// speichert den kleinsten Wert aus pq in val und entfernt ihn
// liefert true bei Erfolg, false wenn leer
bool get(priqueue *pq, int *val)
{
  int i, j, s;
  int v;
  
  if (pq->cnt == 0) return false;
  
  *val = pq->arr[1];    // Ergebnis = vorderstes Element
  v = pq->arr[pq->cnt]; // v = hinterstes Element
                        // wird hinten entfernt und muss von vorne "einsickern"
  --(pq->cnt);          // arr wird 1 kürzer

  i = 1;           // i = Index des "Loches" = Vater
                   // Am Anfang: Platz des entfernten, vordersten Elementes
  s = 1;           // s = Index des ausgewählten (kleineren Sohnes)
  for (;;) {
    j = 2 * i;     // j = Index des linken Sohnes
    if ((j <= pq->cnt) && (pq->arr[j] < v)) {
      // linker Sohn existiert und ist kleiner einsickerndem Element
      s = j;    // ==> linker Sohn ist Kandidat zum nach vorne Schieben
      ++j;      // stelle j auf rechten Sohn
      if ((j <= pq->cnt) && (pq->arr[j] < pq->arr[s])) {
        // rechter Sohn existiert und ist noch kleiner
        s = j;  // ==> rechter Sohn wird nach vorne geschoben
      }
    }
    else {
      // linker Sohn ist nicht vorhanden oder größer v
      ++j;      // stelle j auf rechten Sohn
      if ((j <= pq->cnt) && (pq->arr[j] < v)) {
        // rechter Sohn existiert und ist kleiner einsickerndem Element
        s = j;  // ==> rechter Sohn wird nach vorne geschoben
      }
    }
  
    if (s == i) {  // kein Sohn ist kleiner v
      // ==> Verschieben ist fertig, v gehört an Stelle i
      pq->arr[i] = v;  
      return true;
    }

    pq->arr[i] = pq->arr[s];  // schiebe den gewählten Sohn in das Loch
    i = s;                    // Platz des Sohnes ist neues Loch
  }
}

int main(int argc, const char *argv[])
{
  int i;
  priqueue queue;

  queue.cnt = 0;

  for (i = 1; i < argc; ++i) {
    if (!put(&queue, atoi(argv[i]))) {
      fprintf(stderr, "%s: Too many values (%d, max. %d)\n",
              argv[0], argc - 1, SIZE - 1);
      exit(EXIT_FAILURE);
    }
  }

  while (get(&queue, &i)) {
    printf("%d ", i);
  }
  putchar('\n');

  exit(EXIT_SUCCESS);
}