Heapificar a Heap

Existem duas operações principais que podem ser realizadas numa Heap: podemos adicionar um elemento e remover o nó raiz da Heap.

Depois de realizar cada uma dessas operações, precisamos garantir que as propriedades da Heap não sejam violadas.

Ao remover a raiz, devemos percorrer do topo até a base da Heap, modificando-a e ajustando a estrutura para ter a certeza de que todos os nós-pai tenham um valor maior do que os seus nós-filhos (para um max-heap).

Ao adicionar um elemento, precisamos ir de baixo para cima e modificar a estrutura, garantindo que todos os nós-pai tenham valor maior que seus nós-filhos.

Inserir um Novo Elemento numa Heap

Para inserir um novo valor, primeiro adicionamos esse valor ao final do array. Em seguida, a propriedade da Heap é restaurada trocando repetidamente o item recém-inserido com o seu nó-pai, caso a propriedade não seja satisfeita entre pai e filho:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Heap inicial
heap.append(6)                        # Adicionar um novo elemento com valor 6

# Subir e corrigir a propriedade da Heap
node = len(heap) - 1                  # O índice do nó atual
while node > 1:                       # Enquanto não chegamos à raiz
    parent = node // 2                # Obter o índice do nó-pai
    if heap[node] > heap[parent]:     # Se a estrutura da Heap não está correta
        heap[node], heap[parent] = heap[parent], heap[node]
    else:                             # Se a estrutura está correta
        break                         # Então os acima também estão em ordem => parar
    node //= 2                        # Ir para o nó-pai

Eliminar o Elemento Raiz de uma Heap

Para eliminar o elemento raiz, primeiro ele é substituído pelo último item do array. Em seguida, a propriedade da Heap é restaurada trocando repetidamente o nó com seu maior filho (no caso de uma max-heap) até que o nó esteja na posição correta:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Heap inicial
heap[1], heap[-1] = heap[-1], heap[1] # Trocar a raiz com o último elemento
heap.pop()                            # Remover o último elemento (anteriormente a raiz)

# Descer e corrigir a propriedade da Heap
node = 1                              # O índice do nó atual
while node < len(heap):               # Enquanto não chegamos ao fim
    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')
    
    # Se a propriedade da Heap não foi violada => parar aqui
    if heap[node] >= left and heap[node] >= right:
        break
    
    # Se left > right => Devemos mover na direção da esquerda
    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

Desafio: Corrigir a Heap

Dada uma min-heap com n números, todos os n-1 primeiros números satisfazem a propriedade de min-heap. O n-ésimo número pode violar essa propriedade. O objetivo é corrigir a Heap de forma que todos os números realmente cumpram a condição de min-heap.

Entrada

A primeira linha da entrada contém um único inteiro n (1 ≤ n ≤ ).

A próxima linha contém n inteiros separados por espaço () que representam os valores dos elementos na Heap.

Saída

O programa deve imprimir n inteiros separados por espaço, representando a Heap corrigida.

Exemplos

Entrada	Saída
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

Explicação

Exemplo 1

Exemplo 2