Алгоритм пирамидальной сортировки (Heap sort)
Пирамидальная сортировка — это алгоритм сортировки, основанный на сравнении элементов, который использует структуру данных под названием куча (heap) для упорядочивания массива. Основная идея алгоритма заключается в том, чтобы сначала построить кучу из элементов массива, а затем многократно извлекать наибольший/наименьший элемент из кучи (в зависимости от того, является ли она макс-кучей (max-heap) или мин-кучей (min-heap)) и перемещать этот элемент в конец массива, пока куча не опустеет.
Вам требуется реализовать алгоритм пирамидальной сортировки, используя мин-кучу (min-heap).
Входные данные
Первая строка содержит целое число
n (1 ≤ n ≤ 100 000) — количество элементов.Следующая строка содержит
n целых чисел, разделённых пробелами: (). Эти значения необходимо отсортировать.Выходные данные
Программа должна вывести итоговый отсортированный массив в порядке возрастания.
Примеры
Входные данные | Выходные данные |
7
4 3 8 -2 9 0 2 | -2 0 2 3 4 8 9 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB