void heapify(int* arr, int n, int i)
{
    int largest = i; // Присваиваем наибольшему корень
    int l = 2 * i + 1; // левый = 2*i + 1
    int r = 2 * i + 2; // правый = 2*i + 2

    // Если левый больше корня
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // Если левый больше корня
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // Если больший не корень
    if (largest != i)
    {
        swap(&arr[i], &arr[largest]);

        //Рекурсивно "хиппуем" поддерево от наибольшей величины
        heapify(arr, n, largest);
    }
}

// главная функция для хип сорта
void heapSort(int* arr, int n)
{
    // Строим кучу
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // Вытягиваем элементы по одному
    for (int i = n - 1; i >= 0; i--)
    {
        // Меняем текущий корень в конец
        swap(&arr[0], &arr[i]);


        heapify(arr, i, 0);
    }
}