🔥

문제

최소 힙을 구현해보자.


  1. 힙에 자연수 x를 넣는다.


  1. 현재 가장 작은 값을 출력하고, 그 값을 최소 힙에서 제거한다.


처음에는 비어 있는 힙에서 시작한다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.


다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 x를 추가하는 1번 연산이고, x가 0이라면 2번 연산을 의미한다. x는 2^31보다 작다.

출력

입력에서 0이 주어질 때마다 답을 한 줄로 출력한다. 만약 힙이 비어 있는데 0이 주어진 경우에는 0을 출력하면 된다.

예제 1 입력

9
0
12345678
1
2
0
0
0
0
32

예제 1 출력

0
1
2
12345678
0

Source

n = int(input())
tree = [0 for _ in range(n + 1)]
size = 0

def swap(i, j):
    tmp = tree[i]
    tree[i] = tree[j]
    tree[j] = tmp

def add(x):
    global size
    size += 1
    tree[size] = x

    idx = size
    while(idx > 1):
        if(tree[idx] < tree[idx // 2]):
            swap(idx, idx // 2)
        else:
            break

        idx //= 2

def remove():
    global size
    if(size == 0):
        return 0

    top = tree[1]
    tree[1] = tree[size]
    tree[size] = 0
    size -= 1

    idx = 1
    while(idx * 2 <= size):
        l = idx * 2
        r = idx * 2 + 1

        # r이 존재하지 않거나, 왼쪽 자식이 오른쪽 자식보다 작고
        # x값이 왼쪽 자식보다 크면
        if((r > size or tree[l] < tree[r]) and tree[idx] > tree[l]):
            swap(idx, l)
            idx = l
        # r이 존재하고 x값이 오른쪽 자식보다 크면
        elif(r <= size and tree[idx] > tree[r]):
            swap(idx, r)
            idx = r
        else:
            break

    return top

for i in range(n):
    x = int(input())

    if(x == 0):
        print(remove())
    else:
        add(x)

참고