백준 1927 - 최소 힙 (파이썬)

Answer

import sys

def insert(heap, num):
    heap.append(num)
    i = len(heap) - 1

    while i > 1:
        if heap[i] < heap[i // 2]:
            heap[i], heap[i // 2] = heap[i // 2], heap[i]
            i //= 2
        else:
            break

def remove(heap):
    min_val = heap[1]
    tmp = heap.pop()

    parent = 1
    child = 2
    heap_len = len(heap)

    while child <= heap_len - 1:
        if child < heap_len - 1 and heap[child] > heap[child + 1]:
            child += 1

        if heap[child] >= tmp:
            break

        heap[parent] = heap[child]

        parent = child
        child *= 2

    if heap_len != 1:
        heap[parent] = tmp

    return min_val

n = int(sys.stdin.readline())
heap = [0]

for _ in range(n):
    num = int(sys.stdin.readline())

    if num == 0:
        if len(heap) == 1:
            print(0)
        else:
            print(remove(heap))
    else:
        insert(heap, num)