[BOJ] 최소 힙

---

코드

import sys
input = sys.stdin.readline

N = int(input())

# 배열 인덱스로 구현하는 완전이진트리
# 루트노드 인덱스: 1
# 노드 n의 자식노드 인덱스: 2n, 2n+1
# 노드 n의 부모노드 인덱스: n // 2

heap = [0]

def delete():
    # 비어있으면 0출력
    if len(heap) <= 1:
        print(0)
        return
        
    # 1. 루트노드(최소값)를 먼저 저장해 둔 후 마지막 노드와 swap
    root = heap[1]
    heap[1], heap[-1] = heap[-1], heap[1]
    # 2. 마지막 노드(루트노드였던것) 삭제
    heap.pop()
    # 3. 루트노드 숫자를 재배열(자식노드와 비교하면서 자신이 더 큰 숫자인 경우 swap)
    idx = 1
    while(True):
        child = idx * 2
        # 최소 힙은 두 자식 노드 중 작은 값을 가진 노드와 swap한다.
        if(child+1 < len(heap) and heap[child] > heap[child+1]):
            child += 1
        if(child >= len(heap) or heap[child] > heap[idx]): break
        heap[idx], heap[child] = heap[child], heap[idx]
        idx = child
    print(root)

def insert(x):
    # 1. 마지막 노드에 x를 삽입
    heap.append(x)
    
    # 2. 부모 노드와 비교하면서 자신이 더 작은 숫자인 경우 swap
    # 3. 조건을 만족하지 않거나 루트노드가 된 경우 종료
    idx = len(heap) - 1
    while(idx != 1 and x < heap[idx // 2]):
        heap[idx], heap[idx // 2] = heap[idx // 2], heap[idx]
        idx = idx // 2
    
    

for _ in range(N):
    query = input().rstrip()
    if query == '0':
        delete()
    else:
        insert(int(query))

결과

풀이 방법

• 최소 힙에 대한 개념과 구현방법을 연습하는 문제였다.
• 참고자료: 링크

---