Пирамидальная сортировка

 #include <stdio.h>

// Функция для обмена значениями двух переменных

void swap(int *a, int *b) {

    int temp = *a;

    *a = *b;

    *b = temp;

}

// Просеивание вверх (итеративное)

void heapifyUp(int arr[], int i) {

    while (i > 0) {

        int parent = (i - 1) / 2;

        

        if (arr[i] > arr[parent]) {

            swap(&arr[i], &arr[parent]);

            i = parent; 

        } else {

            break; 

        }

    }

}

// Просеивание вниз (итеративное — без рекурсии)

void heapifyDown(int arr[], int n, int i) {

    int largest = i;

    while (1) {

        int left = 2 * i + 1;  // Левый потомок

        int right = 2 * i + 2; // Правый потомок

        // Ищем наибольший элемент среди текущего узла и его детей

        if (left < n && arr[left] > arr[largest])

            largest = left;

        if (right < n && arr[right] > arr[largest])

            largest = right;

        // Если корень и так самый большой, куча стабильна

        if (largest == i) {

            break;

        }

        // Если нашелся элемент больше, меняем их местами

        swap(&arr[i], &arr[largest]);

        // Спускаемся ниже по дереву

        i = largest;

    }

}

// Основная функция пирамидальной сортировки

void heapSort(int arr[], int n) {

    // 1. Строим Max-Heap вставкой по одному элементу

    for (int i = 1; i < n; i++) {

        heapifyUp(arr, i);

    }

    // 2. Сортируем массив

    for (int i = n - 1; i > 0; i--) {

        swap(&arr[0], &arr[i]); // Переносим максимум в конец

        heapifyDown(arr, i, 0); // Просеиваем новый корень вниз

    }

}

// Функция для вывода массива

void printArray(int arr[], int size) {

    for (int i = 0; i < size; i++) {

        printf("%d ", arr[i]);

    }

    printf("\n");

}

int main() {

    int arr[] = {12, 11, 13, 5, 6, 7};

    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Исходный массив:\n");

    printArray(arr, n);

    heapSort(arr, n);

    printf("Отсортированный массив:\n");

    printArray(arr, n);

    

    return 0;

}