Преобразование в кучу (Heapify the Heap)

С кучей (Heap) можно выполнять два основных действия: добавлять элемент и удалять корневой узел.

После выполнения каждой из этих операций необходимо убедиться, что свойства кучи не нарушены.

При удалении корня мы идём сверху вниз и устраняем несоответствия в структуре, чтобы каждое родительское значение оставалось больше (для max-кучи), чем значения в дочерних узлах.

При добавлении элемента, наоборот, мы движемся снизу вверх, следя за тем, чтобы значение в родительских узлах оставалось больше, чем в дочерних.

Insert a New Element Into a Heap

Чтобы вставить новое значение, мы сначала размещаем его в конце массива, а затем восстанавливаем свойство кучи, многократно обменивая местами вставленный элемент с его родителем, если структура кучи нарушена:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Initial heap
heap.append(6)                        # Add a new element with a value of 6

# Float up and fix the heap property
node = len(heap) - 1                  # The index of the current node
while node > 1:                       # While we haven't reached the root
    parent = node // 2                # Get the index of the parent node
    if heap[node] > heap[parent]:     # If the heap structure is not correct
        heap[node], heap[parent] = heap[parent], heap[node]
    else:                             # If the structure is correct
        break                         # Then the above ones are also in place => stop
    node //= 2                        # Move to the parent node

Delete the Root Element of a Heap

Чтобы удалить корневой элемент, его сначала меняют местами с последним элементом в массиве, а затем восстанавливают свойство кучи, многократно обменивая местами текущий узел с его наибольшим потомком (для max-кучи), пока узел не окажется на корректном месте:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Initial heap
heap[1], heap[-1] = heap[-1], heap[1] # Swap the root with the last element
heap.pop()                            # Remove the last element (previously root)

# Descend and fix the heap property
node = 1                              # The index of the current node
while node < len(heap):               # While we haven't reached the end
    left = heap[2 * node] if 2 * node < len(heap) else float('-inf')
    right = heap[2 * node + 1] if 2 * node + 1 < len(heap) else float('-inf')
    
    # If the heap property is not violated => stop here
    if heap[node] >= left and heap[node] >= right:
        break
    
    # If left > right => We should move in the left direction
    if left > right:
        heap[2 * node], heap[node] = heap[node], heap[2 * node]
        node = 2 * node
    else:
        heap[2 * node + 1], heap[node] = heap[node], heap[2 * node + 1]
        node = 2 * node + 1

Задание: исправьте кучу

Дана min-куча из n чисел. Гарантируется, что первые n-1 чисел удовлетворяют свойству min-кучи, однако n-е число может его нарушать. Ваша задача — исправить кучу так, чтобы все узлы снова удовлетворяли свойству min-кучи.

Входные данные

В первой строке входных данных дано одно целое число n (1 ≤ n ≤ ).

Во второй строке содержится n целых чисел (), разделённых пробелами, которые представляют значения элементов кучи.

Выходные данные

Программа должна вывести n целых чисел, разделённых пробелами, соответствующих исправленной куче.

Примеры

Входные данные	Выходные данные
7 1 2 5 4 3 6 -3	-3 2 1 4 3 6 5
6 5 6 9 20 10 8	5 6 8 20 10 9

Пояснения

Пример 1

Пример 2