Дан массив. Требуется преобразовать его в кучу с помощью процедуры просеивания вверх.
В первой строке вводится длина массива \(N\). В следующей строке идут элементы массива — \(N\) целых чисел, каждое из которых не превышает по модулю \(10^9\). (\(0 \leq N \leq 10^5\)).
Выведите \(N\) целых чисел — элементы кучи по порядку.
| Ввод | Вывод |
|---|---|
6 1 2 3 4 5 6 |
6 4 5 1 3 2 |
Дана куча размера \(N > 1\). Требуется \(N - 1\) раз выполнить извлечение максимального элемента. Как рассказано выше, в процессе выполнения процедуры Extract_Max последний элемент кучи помещается в её корень, а затем просеивается вниз вызовом Sift_Down. После каждого выполнения процедуры Extract_Max нужно будет вывести индекс конечного положения этого элемента после просеивания, а также значение извлечённого максимального элемента.
В первой строке задан размер кучи \(N \in [2; 10^5]\). Во второй строке вводится сама куча — \(N\) различных целых чисел, каждое из диапазона \([-10^9; 10^9]\). (Гарантируется, что эти числа составляют корректную максимальную кучу).
Требуется вывести \(N - 1\) строку, в каждой — два числа. Первое — индекс конечного положения элемента после его просеивания; второе — значение извлечённого элемента.
| Ввод | Вывод |
|---|---|
6 12 6 8 3 4 7 |
3 12 3 8 2 7 1 6 1 4 |
Требуется реализовать с помощью кучи приоритетную очередь, поддерживающую две операции: добавить элемент и извлечь максимальный элемент.
В следующих задачах в куче могут встречаться равные элементы. Это создаёт некоторый произвол при выполнении процедур SiftUp и SiftDown. Для однозначности ответа его придётся ограничить. Поэтому введём два правила:
1) Процедуры просеивания не должны перемещать элемент дальше, чем это действительно необходимо. Например, если A[i] =A[2*i], то вызов SiftUp(2*i) не должен менять местами эти два элемента (хотя их обмен и не испортит кучу, он бесполезен).
2) Если при просеивании вниз можно перемещать рассматриваемый элемент как влево вниз, так и вправо вниз (это бывает, когда он меньше двух равных дочерних), то следует выбирать направление влево. Втрое правило довольно произвольно и введено лишь для обеспечения однозначности ответа. Первому правилу, напротив, должна удовлетворять любая разумная реализация кучи.
В первой строке вводятся два числа — максимальный размер приоритетной очереди \(N\) и количество запросов \(M\). (\(1 \leq M, N \leq 10^5\)). Далее идут \(M\) строк, в каждой строке — по одному запросу. Первое число в запросе задаёт его тип, остальные числа (если есть) — параметры запроса. Тип \(1\) — извлечь максимальный (без параметров). Тип \(2\) — добавить данный элемент в очередь. Запрос имеет один параметр — число из диапазона \([-10^9; 10^9]\).
В ответ на запрос типа \(1\) следует вывести: 1) Если извлекать было нечего (очередь пуста), то \(-1\). 2) Иначе — два числа: первое — индекс конечного положения элемента после его просеивания (если же удалён был последний элемент и просеивать осталось нечего, вывести \(0\)); второе — значение извлечённого элемента.
В ответ на запрос типа \(2\) следует вывести: 1) Если добавить нельзя (нет места, поскольку в очереди уже \(N\) элементов), то вывести \(-1\). (При этом куча не должна измениться). 2) Иначе — индекс добавленного элемента.
Кроме того, после выполнения всех запросов требуется вывести кучу в её конечном состоянии.
| Ввод | Вывод |
|---|---|
4 7 1 2 9 2 4 2 9 2 9 2 7 1 |
-1 1 2 3 2 -1 2 9 9 4 9 |
Требуется отсортировать по неубыванию с помощью изученного алгоритма целочисленный массив размера \(N\).
В первой строке вводится длина массива \(N\). В следующей строке идут элементы массива — \(N\) целых чисел, каждое из которых не превышает по модулю \(10^9\). (\(1 \leq N \leq 10^5\)).
Выведите \(N\) чисел — элементы исходного массива в порядке неубывания.
| Ввод | Вывод |
|---|---|
6 10 4 2 2 1 6 |
1 2 2 4 6 10 |
Условие этой задачи отличается от условия предыдущей лишь наличием ещё одного типа запроса — запроса на удаление заданного (не обязательно максимального) элемента. Это будет запрос типа \(3\) с единственным параметром, задающим индекс элемента, который требуется удалить из кучи.
В первой строке вводятся два числа — максимальный размер приоритетной очереди \(N\) и количество запросов \(M\). (\(1 \leq M, N \leq 10^5\)). Далее идут \(M\) строк, в каждой строке — по одному запросу. Тип \(1\) — извлечь максимальный. Тип \(2\) — добавить элемент. Тип \(3\) — удалить элемент с заданным индексом.
Вывод для запросов типа \(1\) и \(2\) аналогичен предыдущей задаче.
В ответ на запрос типа \(3\) следует вывести: 1) \(-1\), если элемента с таким индексом нет и удаление невозможно. (При этом куча не должна измениться). 2) Иначе — значение удаленного элемента. Гарантируется, что параметр является неотрицательным целым не больше \(10^9\).
Кроме того, после выполнения всех запросов требуется вывести кучу в её конечном состоянии.
| Ввод | Вывод |
|---|---|
4 10 1 2 9 2 4 2 9 2 9 2 7 1 3 4 2 1 3 3 |
-1 1 2 3 2 -1 2 9 -1 4 9 9 4 1 |