Python - < 10 >

개요

힙을 배열에 1번부터 담으면 인덱스를 이진수로 쓴 것만으로 루트에서 그 노드까지 가는 길이 나온다. i >> 1이면 부모로 한 칸 올라가고, 맨 앞 1을 뺀 나머지 비트를 읽으면 왼쪽·오른쪽 순서가 된다. 오늘 배운 것 중에 이게 제일 신기했다!

마지막에 푼 힙 문제도 이 >> 1로 부모를 따라 올라가는 풀이였는데, 정작 틀린 곳은 올라가는 루프가 아니라 힙을 만드는 방식이었다.

수업은 트리 BFS에서 시작해 이진 탐색 트리( BST ), 힙 순서로 나갔고, 강의 뒤에는 AI가 던지는 질문에 답하면서 이해한 걸 확인했다. Python - < 9 >의 Prim에서 쓰던 heapq가 안에서 어떻게 움직이는지도 이번에 같이 봤다.

• 트리 BFS: 레벨 순서를 만드는 건 트리가 아니라 큐
• BST: 정렬 배열 대신 쓰는 이유, 높이를 정하는 삽입 순서, 삭제할 때 올라올 수 있는 값
• 힙: 규칙을 약하게 만들고 얻은 것, 비트 연산 인덱스, heapify가 O(N)인 이유
• heapq 실무 패턴: 최대 힙, 동순위 비교, 지연 삭제
• 이진 힙 문제: 올바른 힙과 문제가 원하는 힙

---

트리 BFS — 순서는 큐가 만든다

BFS는 후보를 큐에 넣고 넣은 순서대로( FIFO ) 꺼낸다. 그래서 루트 A의 자식 B, C가 먼저 들어가고, B를 꺼낼 때 B의 자식 D, E가 C 뒤에 줄을 선다. 꺼내는 순서는 A B C D E F …, 위층부터 한 층씩이다.

from collections import deque

# 부모 -> 자식 방향으로만 저장한 트리
tree = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F']}

def bfs(root):
    queue = deque([root])  # 꺼낼 후보
    order = []
    while queue:
        node = queue.popleft()  # 먼저 넣은 것부터 꺼냄
        order.append(node)
        for child in tree.get(node, []):  # 리프는 키가 없어서 get으로 빈 리스트
            queue.append(child)
    return order

print(bfs('A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

tree[node]로 쓰면 리프 D, E, F는 딕셔너리에 키가 없어서 KeyError가 난다. 그래서 get으로 빈 리스트를 받는다.

• 깊이 k+1 노드는 깊이 k 노드를 꺼낼 때 큐에 들어간다
• FIFO라서 뒤에 들어온 깊이 k+1 노드는 아직 남은 깊이 k 노드를 추월하지 못한다

같은 코드에서 큐를 스택으로만 바꾸면 DFS가 된다. 자식을 역순으로 push하면 재귀 전위 순회와 같은 순서로 나온다. 탐색 순서는 “후보를 꺼내는 규칙”이 정한다.

visited가 없어도 되는 조건

트리 BFS에 visited가 없어도 되는 건 자식마다 부모가 하나뿐이라서 같은 노드가 두 번 들어올 길이 없기 때문이다. 단, 위 코드처럼 부모 → 자식 방향으로만 저장했을 때 얘기다. 간선을 양방향으로 저장하면 자식에서 부모로 되돌아갈 수 있으니 visited나 parent 인자가 다시 필요하다.

pop(0) 대신 deque

list.pop(0)은 맨 앞을 빼고 뒤 원소를 전부 한 칸씩 당긴다( shift ). 한 번에 O(N)이라 BFS 전체로는 O(N²)이 된다. deque.popleft()는 O(1)이라 BFS가 O(N)으로 끝난다.

CPython의 deque는 원소 64개짜리 블록을 양방향 연결 리스트로 이은 구조다( Modules/_collectionsmodule.c의 BLOCKLEN ). 양 끝 블록에서만 넣고 빼니 shift가 없다.

BFS가 최단 거리를 주는 이유

BFS는 출발점에서 바깥으로 한 겹씩 퍼진다. DFS는 한 방향으로 끝까지 가다가 도착한 것이라 처음 도착한 경로가 최단이라는 보장이 없다.

조금 더 정확히 말하면 BFS가 꺼내는 거리 값은 줄어들지 않는다. 그래서 어떤 칸을 처음 꺼낸 순간의 거리가 최단이다. 전제는 모든 간선 비용이 같을 것이고, 비용이 다르면 우선순위 큐를 쓰는 다익스트라로 넘어간다.

게임에 붙여 보면, 몬스터마다 플레이어까지 길을 따로 찾지 않고 플레이어 위치에서 BFS를 한 번 돌려 맵 전체에 거리값을 깔아둘 수 있다. 몬스터는 자기 칸 주변에서 거리가 더 작은 칸으로만 움직이면 된다( flow field ). 실제로 구현해 보지는 않은 응용이다.

---

BST — 정렬 배열의 삽입 비용을 피하는 구조

정렬된 배열은 이진 탐색으로 자리를 O(logN)에 찾지만, 그 자리에 넣거나 빼려면 뒤 원소를 전부 밀어야 해서 O(N)이 든다. BST는 자리를 찾은 뒤 포인터 하나만 바꾼다. 비용은 트리 높이만큼이다.

탐색할 때 비교 한 번으로 한쪽을 통째로 버릴 수 있는 건 순서 속성이 서브트리 전체에 걸려 있기 때문이다. 루트가 10이면 왼쪽 서브트리의 모든 값이 10보다 작다. “부모와 바로 아래 자식만 비교”하는 규칙이었다면 손자 쪽에 큰 값이 숨어 있을 수 있어 버릴 수 없다. BST 검증 문제에서 자주 빠지는 함정이 이거다.

새 값은 항상 리프 자리에 붙는다. 기존 노드 사이의 연결은 하나도 건드리지 않으니 순서 속성이 그대로 유지된다.

높이는 삽입 순서가 정한다

같은 1~5를 넣어도 순서에 따라 모양이 다르다.

삽입 순서	모양	높이
1, 2, 3, 4, 5	오른쪽으로만 이어진 편향 트리	4
3, 1, 4, 2, 5	3 아래 1·4, 1 아래 2, 4 아래 5	2

노드 N개일 때 최대 높이는 편향 트리의 N−1이다. 최소 높이는 높이 h인 트리에 최대 2^(h+1)−1개가 들어간다는 데서 2^(h+1)−1 ≥ N을 풀면 나온다. 높이는 정수라서 올림을 해야 하고, ⌈log₂(N+1)⌉ − 1 = ⌊log₂N⌋이다.

게임에서 생성 ID나 생성 시간처럼 계속 커지기만 하는 키를 그대로 BST에 넣으면 1, 2, 3, 4, 5 순서와 같은 상황이 돼서 편향 트리가 된다.

배열보다 느린 지점

BST는 노드를 하나씩 따로 할당하니 메모리에 흩어져 있다. 이게 캐시 쪽에서 두 가지로 손해를 본다.

• 이웃한 노드가 같은 캐시 라인에 있을 가능성이 낮아 미스가 잦다
• 자식 주소는 지금 노드를 읽어야 알 수 있다( pointer chasing ). 다음에 읽을 곳을 미리 가져올 수가 없다

재귀 대신 반복문

def search(root, key):
    node = root
    while node:  # 재귀 호출 대신 한 칸씩 내려감
        if key == node.key:
            return node
        node = node.left if key < node.key else node.right  # 순서 속성으로 한쪽만 선택
    return None

재귀 _search를 반복문으로 바꾸면 추가 공간이 O(h)에서 O(1)이 되고, 편향 트리에서도 스택 오버플로가 나지 않는다. CPython 기본 재귀 한도는 1000이다( sys.getrecursionlimit() ).

트리가 불균형해져도 노드 메모리 총량은 같다. 늘어나는 건 재귀 스택이었는데, 이건 반복문으로 없앨 수 있다. 반복문으로도 못 없애는 근본 비용은 탐색 시간 O(N)이다.

---

BST 삭제 — 그 자리에 올 수 있는 값

삭제는 대상 노드의 자식 수에 따라 갈린다.

• 리프: 그냥 떼어낸다
• 자식 하나: 자식 서브트리를 그 자리로 올린다. 10의 왼쪽 자식을 지우는 경우라면, 올라오는 서브트리는 원래부터 10의 왼쪽에 있었으니 10보다 작다는 게 이미 보장돼 있다
• 자식 둘: 다른 값을 가져와 그 자리를 채운다

자식 둘일 때 대체값의 조건

15를 지우는데 15의 왼쪽에 12, 오른쪽에 18이 있고 18의 왼쪽에 17이 있다고 하자. 18을 15 자리에 올리면 17이 18보다 작은데 오른쪽 서브트리에 남아 깨진다. 왼쪽의 12( 중위 전임자 )는 올릴 수 있다.

대체값은 왼쪽 서브트리 전체보다 크고 오른쪽 서브트리 전체보다 작아야 한다.

처음엔 이 자리에 올 수 있는 게 삭제 노드의 자식들뿐이라고 생각했다. 그런데 17 아래에 16이 더 달린 트리에서 중위 후속자를 찾아보니 자식이 아니라 손자인 16이었다. 정리하면 올 수 있는 값은 정렬 순서상 바로 앞( 전임자 )이나 바로 뒤( 후속자 )이고, 트리에서 몇 칸 아래에 있는지와는 상관없다.

후속자는 오른쪽 서브트리에서 왼쪽으로 끝까지 내려가서 찾는다. while current.left가 멈추는 곳이니 후속자에게는 왼쪽 자식이 없다. 있었다면 그게 더 작은 최솟값이었을 것이다. 그래서 후속자를 원래 자리에서 지우는 건 항상 리프나 자식 하나 경우로 끝나고, 삭제 전체가 O(h)다.

부모 필드에 반환값을 대입하는 이유

def _delete(node, key):
    if node is None:
        return None
    if key < node.key:
        node.left = _delete(node.left, key)  # 부모가 자기 필드를 직접 갱신
    elif key > node.key:
        node.right = _delete(node.right, key)
    else:
        if node.left is None:  # 자식이 없거나 오른쪽만 있음
            return node.right  # 이 자리에 올 노드를 부모에게 돌려줌
        if node.right is None:  # 왼쪽만 있음
            return node.left
        succ = node.right  # 자식 둘: 중위 후속자 탐색
        while succ.left:
            succ = succ.left
        node.key = succ.key  # 후속자 값을 복사
        node.right = _delete(node.right, succ.key)  # 원래 후속자 노드 삭제
    return node  # 바뀌지 않았으면 자기 자신

함수 안에서 node = None을 해도 부모의 left/right는 여전히 원래 노드를 가리킨다. 지역 변수 이름만 다른 걸 가리키게 바뀌었을 뿐이다. 연결을 바꿀 수 있는 건 그 필드를 가진 부모뿐이라, 자식은 “이 자리에 올 노드”를 반환하고 부모가 대입한다. 루트를 지울 때도 root = _delete(root, key)로 같은 경로를 탄다. C++이라면 Node*&로 부모 필드 자체를 넘기는 방법도 있다.

값 복사 삭제가 남기는 문제

위 코드는 후속자의 값을 복사한다. 그래서 실제로 메모리에서 사라지는 건 원래 후속자 노드고, 지우려던 노드는 후속자 값으로 덮어써진 채 남는다. 여기서부터는 사고 실험이다.

• 후속자 노드를 포인터로 들고 있던 시스템은 해제된 메모리를 가리킨다( C++이면 dangling pointer, 미정의 동작 )
• 지운 노드를 들고 있던 시스템은 오류 없이 다른 객체를 보게 된다

값을 복사하지 않고 노드 자체를 재연결하도록 구현하거나, 바깥에서는 포인터 대신 ID·핸들로 참조하면 피할 수 있다. C++ std::map은 노드를 재연결하는 쪽이라 erase할 때 지운 원소의 반복자·참조만 무효화되고 나머지는 그대로다( cppreference std::map::erase ).

---

중복 키와 컨테이너 고르기

중복 10을 넣으면 위 구현 기준으로 오른쪽으로 들어간다. 중복을 허용할지는 설계 선택이다( C++의 map/set과 multimap/multiset ). 허용하면 search는 위쪽에 있는 원래 10을 찾고 delete는 하나만 지우니, 몇 개를 지울지 규칙이 따로 필요하다.

• 점수를 키로 쓰면 동점이 있으니 중복 허용
• 플레이어 ID를 키로 쓰면 중복 불허
• 동점을 깔끔하게 다루려면 (점수, 플레이어ID) 복합 키로 만들어 중복 자체를 없앤다

키 하나로 조회만 하면 unordered_map, “점수 1000~2000 사이”처럼 범위로 꺼내야 하면 정렬된 map을 쓴다. map은 lower_bound로 시작점을 O(logN)에 찾고 K개를 순서대로 읽어 O(logN + K)다. 해시는 순서가 없어서 전부 훑고 정렬해야 한다. unordered_map의 O(1)도 평균이고, 충돌이 몰리면 O(N), rehash가 일어나면 반복자가 무효화된다.

BST를 중위 순회( 왼쪽 → 루트 → 오른쪽 )하면 값이 정렬돼 나온다. 순서 속성이 모든 서브트리에 똑같이 걸려 있으니 어느 서브트리에서든 왼쪽이 먼저, 즉 작은 값이 먼저 나온다. 그래서 BST 검증은 “중위 순회 결과가 엄격히 증가하는가”로 할 수 있다.

---

힙 — 규칙을 약하게 만들고 얻은 것

힙은 “부모가 자식보다 작다( 최소 힙 )”만 지킨다. 형제끼리, 왼쪽·오른쪽 사이의 순서는 따지지 않는다.

• 포기한 것: 특정 값을 빨리 찾는 능력. 순서 규칙이 약해서 BST처럼 한쪽을 버릴 수 없다
• 얻은 것: 최상단 값을 꺼내고 재배치하는 성능

힙 판정은 루트만 보는 게 아니라 모든 부모-자식 쌍이 규칙을 지키는지로 한다. 모양도 조건이라 완전 이진 트리( 마지막 층을 빼면 꽉 차 있고, 마지막 층은 왼쪽부터 채움 )가 아니면 값이 맞아도 힙이 아니다.

높이를 누가 통제하나

BST와 힙 모두 연산 비용은 O(h)다. 차이는 h를 누가 정하느냐다.

	모양을 정하는 것	높이
BST	들어오는 값과 순서	최악 N−1
힙	구조 규칙	항상 ⌊log₂N⌋

규칙이 약하니까 새 원소를 항상 마지막 자리에 둘 수 있고, 그러면 모양이 언제나 완전 이진 트리로 유지된다. 그래서 삽입은 마지막 자리에 넣고 부모와 비교·교환하며 올라가는데, 높이가 logN이니 O(logN)이다.

배열에 담고 비트 연산으로 걷기

완전 이진 트리는 중간에 빈칸이 없어서 배열에 그대로 담을 수 있다. 빈칸을 허용하면 편향 트리 하나에 2^N − 1칸이 필요해진다. 완전 이진 트리 조건이 배열 표현의 전제다.

1번부터 담으면( 0번은 비움 ) 부모·자식 관계가 계산으로 나온다.

관계	산술	비트 연산
부모	i // 2	i >> 1
왼쪽 자식	2 * i	i << 1
오른쪽 자식	2 * i + 1	(i << 1) \| 1

0번 칸 하나를 버리는 대신 공식이 깔끔해진다.

개요에서 신기하다고 한 게 이 표 다음이다. 인덱스를 이진수로 쓰고 맨 앞 1을 떼면, 남은 비트가 루트에서 내려가는 길이다. 0이면 왼쪽, 1이면 오른쪽.

• 6 = 110 → 앞 1을 떼면 10 → 루트(1)에서 오른쪽(3), 거기서 왼쪽(6)
• 5 = 101 → 01 → 왼쪽(2), 오른쪽(5)

<< 1이 왼쪽으로 내려가는 것, | 1이 오른쪽을 고르는 것이니 루트부터 비트를 하나씩 붙여 온 기록이 인덱스에 그대로 남는다. 반대로 >> 1은 마지막 비트를 떼서 한 칸 올라간다.

배열 표현에는 이런 이점도 있다.

• 자식 주소를 노드를 읽기 전에 계산으로 안다( BST의 pointer chasing이 없다 )
• 연속 메모리라 캐시에 잘 맞는다
• 포인터를 저장할 필요가 없다

삭제 — 빈칸을 마지막으로 보낸다

루트를 꺼낸 뒤 빈 루트 자리를 채우는 방법으로, 처음엔 큰 자식( 최대 힙 기준 )을 계속 끌어올리는 방식을 생각했다. 첫 예시에서는 이게 잘 됐는데, 빈칸이 우연히 마지막 칸에서 끝나서 결과가 같았던 것이었다. 빈칸이 5번처럼 마지막이 아닌 자리에 남으면 중간에 구멍이 생겨 완전 이진 트리 조건이 깨진다.

그래서 표준 방식은 마지막 원소를 루트로 옮겨 빈칸을 처음부터 맨 마지막 자리로 정해두고, 루트에서 자식과 비교하며 내려보낸다( siftdown ). 최대 힙에서 내려갈 때는 두 자식 중 큰 쪽과 바꾼다. 작은 자식과 바꾸면 올라온 작은 값이 다른 자식보다 작아져 규칙이 깨진다.

삽입이든 삭제든 힙 연산은 모양을 먼저 맞추고 값은 나중에 맞춘다.

CPython heapq의 heappop은 여기서 한 번 더 비튼다. 마지막 원소를 루트에 놓고 바로 비교하며 내려가지 않고, 작은 자식을 리프까지 끌어올린 뒤 그 빈 리프 자리에 마지막 원소를 넣고 위로 올린다. 소스 주석에 이유가 적혀 있는데, 마지막 원소는 대개 큰 값이라 루트부터 비교해 봐야 일찍 멈추는 경우가 드물어서 비교 횟수를 줄이려는 것이다( Knuth 3권 인용 ).

heapify가 O(N)인 이유

배열 전체를 힙으로 만드는 heapify는 마지막 부모부터 루트까지 거꾸로 siftdown한다. 노드가 많은 아래층은 내려갈 거리가 짧고, 멀리 내려가야 하는 위층은 노드가 적다. 그래서 전체 이동이 N에 수렴한다.

노드 15개 포화 트리로 최대 이동 횟수를 세 봤다.

깊이	노드 수	heapify( 아래로 갈 거리 )	순차 push( 위로 갈 거리 )
0	1	3	0
1	2	2	1
2	4	1	2
3	8	0	3
합	15	1·3 + 2·2 + 4·1 = 11	2·1 + 4·2 + 8·3 = 34

heapify는 많은 노드에 작은 거리가 곱해지고, 순차 push는 많은 노드에 큰 거리가 곱해진다. O(N)과 O(NlogN)의 차이가 여기서 나온다.

heapq.py 소스 주석에도 실측값이 있다. 길이 1000인 무작위 배열에서 heapify()는 비교 약 1,660회, heappush()를 1000번 하면 2,148~2,219회였다고 적혀 있다( 로컬 Python 3.14.3의 heapq.py에서 확인 ).

최솟값과 최댓값이 둘 다 필요하면

최대 힙에서 최솟값은 리프 중 어딘가에 있어서 찾는 데 O(N)이다. 둘 다 자주 필요하면 최대 힙과 최소 힙을 하나씩 둔다. 한쪽에서 꺼낸 원소가 다른 힙에 남아 있으니 그건 지연 삭제( 아래 heapq 패턴 )로 처리해야 한다. C++이라면 양 끝을 모두 O(logN)에 꺼낼 수 있는 std::multiset도 대안이다.

---

heapq 실무 패턴

heapq는 최소 힙만 제공한다. 숫자라면 부호를 뒤집어 넣으면 최대 힙이 되지만, 숫자가 아닌 원소는 그게 안 된다. heapify를 새로 짤 필요는 없고 원소 쪽에서 비교를 뒤집으면 된다.

import heapq

class MaxItem:
    def __init__(self, value):
        self.value = value
    def __lt__(self, other):  # heapq는 < 만 쓰므로 이것만 뒤집으면 됨
        return self.value > other.value

heap = []
for name in ['bat', 'zombie', 'goblin']:
    heapq.heappush(heap, MaxItem(name))
print(heapq.heappop(heap).value)  # zombie ( 사전순 가장 뒤 )

우선순위가 여러 개일 때

“위협도 높은 순, 같으면 거리 가까운 순”이라면 튜플 (-위협도, 거리)로 넣는다. 튜플은 앞 원소부터 비교하고, 위협도는 큰 게 먼저 나와야 하니 부호를 뒤집는다.

(우선순위, 몬스터 객체)로 넣으면 우선순위가 같을 때 몬스터 객체끼리 비교로 넘어가서 TypeError가 난다. 중간에 유일한 값을 끼워 객체까지 가지 않게 막는다.

import heapq, itertools

counter = itertools.count()  # 넣을 때마다 1씩 커지는 순번
heap = []

def push(threat, dist, monster):
    # (-위협도, 거리, 순번, 객체): 앞 셋에서 반드시 승부가 남
    heapq.heappush(heap, (-threat, dist, next(counter), monster))

몬스터 ID를 넣으면 동순위끼리 ID 순으로, 삽입 순번을 넣으면 먼저 들어온 순서( FIFO )로 나온다.

지연 삭제

힙에서 특정 원소를 지우려면 찾는 데만 O(N)이 든다. 그래서 이벤트를 취소할 때는 힙에서 빼지 않고 “취소됨” 상태만 기록해 두고, 꺼낼 때 그 상태면 버린다. 상태를 기록할 메모리가 추가로 든다.

문제가 되는 상황도 있다. 먼 미래 이벤트를 자주 취소하고 다시 등록하면 꺼내지지 않는 죽은 원소가 힙에 계속 쌓인다. 죽은 원소 비율이 정해 둔 임계치를 넘으면 살아 있는 것만 걸러서 heapify로 다시 만드는 식으로 정리한다.

다익스트라의 “꺼낸 거리가 기록된 거리보다 크면 continue“와 Python - < 9 > Prim의 if end in visited: continue가 같은 기법이다.

---

이진 힙 — 올바른 힙과 문제가 원하는 힙

문제. 이진 최소힙에 자연수 N개를 입력 순서대로 넣는다. 넣을 때는 마지막 자리에 두고, 부모보다 작으면 부모와 자리를 바꾸는 걸 반복한다. 다 넣은 뒤 마지막 노드의 조상 노드에 저장된 값의 합을 구한다.

• 입력: 테스트케이스 수 T. 케이스마다 N, 다음 줄에 자연수 N개
• 출력: #테스트케이스번호 조상합

처음엔 heapq.heapify로 힙을 만들고, 0번에 더미를 넣어 1번부터 시작하게 한 뒤 N >>= 1로 부모를 따라 올라가며 더했다.

import heapq

T = int(input())

for test_case in range(1, T + 1):
    N = int(input()) # N = 자연수 갯수
    binary_heap = list(map(int, input().split()))
    # 최소 힙 정렬
    heapq.heapify(binary_heap)
    # 비트 연산자로 최소화 하기 위해 메모리 추가
    binary_heap.insert(0, 0)
    # 부모를 탐색해가며 합 구하기
    parents_sum = 0
    while N > 0:
        # 부모로 이동
        N = N >> 1
        parents_sum += binary_heap[N]

    print(f"#{test_case} {parents_sum}")

마지막 노드 번호가 곧 N이라 N >> 1부터 더하면 조상만 더해진다. 루트를 더한 다음엔 N이 0이 되면서 더미 0을 한 번 더 더하고 끝나는데, 0이라 합에는 영향이 없다.

AI와 이 코드를 같이 보다가 heapify 방식이 문제가 된다는 얘기를 듣고, 입력을 하나씩 heappush로 넣도록 바꿨다.

import heapq

T = int(input())

for test_case in range(1, T + 1):
    N = int(input()) # N = 자연수 갯수
    input_numbers = list(map(int, input().split()))
    # 최소 힙 정렬 siftup 방식
    binary_heap = list()
    for number in input_numbers:
        heapq.heappush(binary_heap, number)
    # 비트 연산자로 최소화 하기 위해 메모리 추가
    binary_heap.insert(0, 0)
    # 부모를 탐색해가며 합 구하기
    parents_sum = 0
    while N > 0:
        # 부모로 이동
        N = N >> 1
        parents_sum += binary_heap[N]

    print(f"#{test_case} {parents_sum}")

둘 다 올바른 최소 힙이다

조상 합 루프는 처음부터 맞았다. 달라진 건 힙을 만드는 방식뿐이다.

heapify는 아래층 부모부터 siftdown하고, 순차 heappush는 원소마다 마지막 자리에서 위로 올린다. 둘 다 규칙을 지키는 최소 힙을 만들지만 배치는 다를 수 있다. 문제는 “입력 순서대로 넣으며 부모와 교환”한 결과를 요구하니 heappush 쪽이어야 한다.

문제 예시 7 2 5 3 4 6은 두 방식 결과가 [2, 3, 5, 7, 4, 6]로 같아서 예시만으로는 차이가 안 드러난다. 8 4 3 2 6을 넣으면 갈린다( 로컬에서 실행 ).

구성 방식	배열( 1번부터 )	5번의 조상	합
heapify	2, 4, 3, 8, 6	2번( 4 ), 1번( 2 )	6
순차 heappush	2, 3, 4, 8, 6	2번( 3 ), 1번( 2 )	5

결과 배치가 답에 영향을 주는 문제라면 힙이 올바른지만 볼 게 아니라 구성 과정까지 문제 설명과 맞춰야 한다. 최솟값만 꺼내 쓰는 문제였다면 더 빠른 heapify가 맞는 선택이다.

binary_heap.insert(0, 0)도 맨 앞에 넣으면서 전체를 한 칸씩 미니까 O(N)이다. 여기서는 한 번만 하니 문제없다.

주석에 적은 “siftup 방식”은 교과서식 이름이다. heapq 소스에서는 이름이 반대로 붙어 있어서, heappush가 위로 올릴 때 쓰는 함수가 _siftdown이고 heapify·heappop이 쓰는 함수가 _siftup이다. 왜 이렇게 이름을 붙였는지는 소스 주석에서 찾지 못했다.

---

소감

기존에 단어나 간단한 개념만 알고 있던걸 구현 방식과 성능, 사용법들을 제대로 학습하니 매우 재밌었던 것 같다!