#include <stdio.h>
#include <stdlib.h>
// Функция "просеивания" через кучу - формирование кучи
void siftDown(int *numbers, int root, int bottom)
{
  int maxChild; // индекс максимального потомка
  int done = 0; // флаг того, что куча сформирована
  // Пока не дошли до последнего ряда
  while ((root * 2 <= bottom) && (!done))
  {
    if (root * 2 == bottom)    // если мы в последнем ряду,
      maxChild = root * 2;    // запоминаем левый потомок
    // иначе запоминаем больший потомок из двух
    else if (numbers[root * 2] > numbers[root * 2 + 1])
      maxChild = root * 2;
    else
      maxChild = root * 2 + 1;
    // если элемент вершины меньше максимального потомка
    if (numbers[root] < numbers[maxChild])
    {
      int temp = numbers[root]; // меняем их местами
      numbers[root] = numbers[maxChild];
      numbers[maxChild] = temp;
      root = maxChild;
    }
    else // иначе
      done = 1; // пирамида сформирована
  }
}
// Функция сортировки на куче
void heapSort(int *numbers, int array_size)
{
  // Формируем нижний ряд пирамиды
  for (int i = (array_size / 2) - 1; i >= 0; i--)
    siftDown(numbers, i, array_size);
  // Просеиваем через пирамиду остальные элементы
  for (int i = array_size - 1; i >= 1; i--)
  {
//меняем элементы местами
    int temp = numbers[0];
    numbers[0] = numbers[i];
    numbers[i] = temp;
//вызов функции просеивающей через кучу уже без i-го элемента
    siftDown(numbers, 0, i - 1);
  }
}
int main()
{
  int a[100];

  int i=0;
  // Заполнение массива введеннымичислами
  printf("Введите ваши числа\n");

  while (scanf("%d", &a[i])==1)
    i++;

  // Вывод элементов массива до сортировки
  for (int j = 0; j<i; j++)
    printf("%d ", a[j]);
  printf("\n");
  heapSort(a, i); // вызов функции сортировки
  // Вывод элементов массива после сортировки
  for (int j = 0; j<i; j++)
    printf("%d ", a[j]);
  printf("\n");
  getchar();
  return 0;
}