완전 이진 트리·힙·우선순위 큐

매번 전체를 정렬하지 않고 가장 중요한 항목 하나를 꺼내고 싶다면 어떤 구조가 필요할까요? 목표는 힙의 두 조건과 배열 인덱스가 트리를 표현하는 방법을 이해하는 것입니다. 리스트 인덱스·정렬·트리라는 용어를 이 본문에서 함께 준비합니다.

개념과 약속

트리는 부모와 자식으로 이어진 계층입니다. 루트는 부모가 없는 시작점, 리프는 자식이 없는 노드입니다. 이진 트리는 자식이 최대 둘입니다. 완전 이진 트리는 마지막 층 전까지 꽉 차고 마지막 층을 왼쪽부터 채운 모양입니다. 이 모양을 층 순서로 리스트에 저장하면 0-based 인덱스 i의 왼쪽 자식은 2i+1, 오른쪽은 2i+2, 부모는 (i-1)//2입니다. 자식 인덱스가 길이 이상이면 해당 자식이 없습니다.

최대 힙은 모든 부모 값이 자식 이상인 구조입니다. 같은 값도 허용합니다. 루트가 최댓값이지만 형제끼리의 순서나 전체 오름차순을 보장하지 않습니다. 최소 힙은 부모가 자식 이하입니다. 우선순위 큐는 중요도가 높은 항목부터 꺼내는 추상적인 약속이고 힙은 이를 구현하는 방법 하나입니다. Python heapq는 기본적으로 최소 힙이라 가장 작은 값을 꺼냅니다.

최대 힙에 삽입할 때는 마지막 칸에 새 값을 붙여 완전 이진 트리의 모양을 지킨 뒤, 부모보다 크면 서로 바꾸며 위로 올라갑니다. 최대 삭제는 루트를 반환하고 마지막 값을 루트로 옮겨 칸 수를 줄인 뒤 아래로 복구합니다. 아래 max_heap_push·max_heap_pop은 이 두 작업을 직접 구현하며 기존 힙을 변경합니다. 빈 힙 삭제는 IndexError입니다. 루트 깊이를 0으로 세면 n≥1인 완전 이진 트리 높이는 floor(log₂ n)입니다.

손으로 상태 추적하기

최대 힙 [9,7,8,2,3,4,6]을 층 순서로 읽습니다.

마지막 부모부터 아래로 고치면 자식 쪽은 이미 힙입니다. sift_down은 둘 중 큰 자식과 필요할 때만 교환해 아래로 내려갑니다. 삽입 예로 [9,7,8]에 10을 붙이면 [9,7,8,10]에서 부모 7, 다음 부모 9와 바꾸어 [10,9,8,7]입니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

def sift_down(values, root, size):
    while 2 * root + 1 < size:
        child = 2 * root + 1
        if child + 1 < size and values[child + 1] > values[child]:
            child += 1
        if values[root] >= values[child]:
            return
        values[root], values[child] = values[child], values[root]
        root = child


def build_max_heap(values):
    result = list(values)
    for root in range(len(result) // 2 - 1, -1, -1):
        sift_down(result, root, len(result))
    return result


def max_heap_push(heap, value):
    """Mutate an existing valid max heap by adding one value."""
    heap.append(value)
    child = len(heap) - 1
    while child:
        parent = (child - 1) // 2
        if heap[parent] >= heap[child]:
            break
        heap[parent], heap[child] = heap[child], heap[parent]
        child = parent


def max_heap_pop(heap):
    """Remove and return the maximum, mutating a valid nonempty max heap."""
    if not heap:
        raise IndexError('empty max heap')
    maximum = heap[0]
    last = heap.pop()
    if heap:
        heap[0] = last
        sift_down(heap, 0, len(heap))
    return maximum


values = [2, 7, 4, 9, 3, 8, 6]
heap = build_max_heap(values)
print(heap)
for child in range(1, len(heap)):
    assert heap[(child - 1) // 2] >= heap[child]
print("부모-자식 검사 통과")
small = [9, 7, 8]
max_heap_push(small, 10)
assert small == [10, 9, 8, 7]
assert max_heap_pop(small) == 10
assert small == [9, 7, 8]
import heapq
queue = []
for priority in [4, 1, 3]:
    heapq.heappush(queue, priority)
print([heapq.heappop(queue) for _ in range(len(queue))])

실행 결과:

[9, 7, 8, 2, 3, 4, 6]
부모-자식 검사 통과
[1, 3, 4]

왜 맞고 언제 끝나는가

마지막 리프는 자체로 힙입니다. 마지막 부모부터 올라가며, 자식 부분이 힙이라는 전제 아래 부모를 큰 자식과 교환해 내려보내면 해당 부분도 힙이 됩니다. 각 내려가기에서 깊이가 증가하고 유한한 높이를 넘을 수 없어 종료합니다. 부모마다 조건을 만족하면 루트부터 어떤 후손까지도 값이 커지지 않으므로 루트가 최대입니다.

비용과 적용 범위

n개를 아래에서 한 번에 힙으로 만드는 비용은 O(n)입니다. 모든 노드가 높이 log n만큼 내려가는 것은 아니며 대부분은 낮은 층에 있어 높이별 합이 선형입니다. 개별 삽입·최상위 삭제는 O(log n), 최상위 확인은 O(1)입니다. 원본 복사와 힙 저장은 O(n) 공간입니다.

스스로 풀어 보기

1. 인덱스 4의 부모는 어디인가요? 길이 7인 힙에서 인덱스 3의 자식이 있나요?
2. [9,7,8]은 최대 힙인가요? 정렬된 목록인가요?

힌트

1. 부모 식과 자식 식을 대입하세요.
2. 최대 힙 조건은 부모와 자식 사이에만 있습니다.

해설

1. 부모는 (4-1)//2=1입니다. 인덱스 3의 자식 후보 7과 8은 길이 밖이라 없습니다.
2. 최대 힙이며 오름차순도 내림차순도 아닙니다. 형제 7과 8의 상대 순서는 힙 조건이 정하지 않습니다.

흔한 오해

부모가 자식보다 반드시 커야 하는 것은 아닙니다. 중복을 허용하는 힙에서는 ≥ 또는 ≤입니다. 1-based 수식을 0-based 목록에 섞지 마세요.

복습과 다음 연결

힙 정렬은 최대를 오른쪽 확정 구간에 보냅니다. Dijkstra는 최소 비용 항목을 꺼냅니다. API는 heapq 공식 문서를 참고하세요.