Remote Training on Programming

Дан массив, представляющий собой пирамиду (heap), т.е. каждый элемент с индексом i больше или равен каждому из своих детей с индексами 2i+1 и 2i+2 (нумерация элементов в массиве идёт с нуля). Требуется выполнить один шаг второго этапа алгоритма пирамидальной сортировки, то есть:

а). нулевой элемент поменять местами с последним

б). уменьшить длину массива на 1

в). выполнить погружение нового нулевого элемента (downheap), чтобы восстановить свойство пирамиды.

Примечание: если во время погружения элемента оба его дочерних элемента окажутся равны, обмен выполняется с тем, что левее

 

Входные данные: в первой строке записано число элементов в массиве N (от 1 до 100),  во второй – элементы исходного пирамидального массива через пробел

 

Выходные данные: получившийся в итоге массив (без последнего элемента)

 

Пример входных данных:

7

9 7 8 7 6 2 4

 

Пример выходных данных:

8 7 4 7 6 2

 

Автор: Насонова Ю.В.