Heapify the Heap

Existen 2 operaciones principales que pueden realizarse sobre un montículo (heap): podemos añadir un elemento y podemos eliminar el nodo raíz.

Tras cada operación, debemos asegurarnos de que no se violen las propiedades del montículo.

Cuando eliminamos la raíz, debemos ir desde la parte superior hasta el fondo del montículo, modificándolo y corrigiendo su estructura para asegurarnos de que todos los nodos padre tengan un valor más grande que el de sus nodos hijos (en el caso de un montículo máximo).

Un ejemplo de un montículo máximo (max-heap) con 8 nodos

Cuando añadimos un elemento, debemos ir desde la parte inferior hasta la parte superior, modificando la estructura para asegurarnos de que todos los nodos padre tengan un valor más grande que el de sus nodos hijos.

Insert a New Element Into a Heap

Para insertar un valor nuevo, primero se añade el valor al final del array, y luego se restaura la propiedad del montículo (heap) intercambiando repetidamente el elemento recién insertado con su nodo padre si no se cumple dicha propiedad:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Montículo inicial
heap.append(6)                        # Agrega un elemento nuevo con valor de 6

# Float up and fix the heap property
node = len(heap) - 1                  # Índice del nodo actual
while node > 1:                       # Mientras no estemos en la raíz
    parent = node // 2                # Índice del nodo padre
    if heap[node] > heap[parent]:     # Si la estructura del montículo no es correcta
        heap[node], heap[parent] = heap[parent], heap[node]
    else:                             # Si la estructura es correcta
        break                         # Entonces las posiciones superiores también lo estarán => detén
    node //= 2                        # Sube al nodo padre

Delete the Root Element of a Heap

Para eliminar el elemento raíz, primero se reemplaza con el último elemento del array y luego se restaura la propiedad del montículo intercambiando repetidamente el nodo con su hijo más grande (en el caso de un montículo máximo), hasta que el nodo se ubique en la posición correcta:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Montículo inicial
heap[1], heap[-1] = heap[-1], heap[1] # Intercambia la raíz con el último elemento
heap.pop()                            # Elimina el último elemento (anteriormente la raíz)

# Descend and fix the heap property
node = 1                              # Índice del nodo actual
while node < len(heap):               # Mientras no alcancemos el final
    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')
    
    # Si no se viola la propiedad del montículo => detén
    if heap[node] >= left and heap[node] >= right:
        break
    
    # Si left > right => Debemos movernos hacia la izquierda
    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

Challenge: Fix the Heap

Se nos da un montículo mínimo (min-heap) con n números, donde se garantiza que los primeros n-1 números cumplen la propiedad de montículo mínimo. El n-ésimo número podría violar dicha propiedad. El reto consiste en arreglar el montículo para que todos los números cumplan la propiedad de montículo mínimo.

Entrada

La primera línea de la entrada contiene un único número entero n (1 ≤ n ≤ ).

La siguiente línea contiene n enteros separados por espacios: (), que representan los valores de los elementos del montículo.

Salida

El programa debe imprimir n enteros separados por espacios que representen el montículo corregido.

Ejemplos

Entrada	Salida
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

Explicación

Ejemplo 1

Ejemplo 2