포인터 없는 트리: 배열 기반 힙

"힙은 종이 위에서는 트리지만 메모리에서는 배열이야. 노드 객체도 없고 left/right 포인터도 없어. 그냥 산술이지. '트리'가 실제로 쓸 수 있는 가장 빠른 구조 축에 들 수 있는 비밀이 여기 있어."

완전성이 배열을 사줘

이진 힙은 언제나 complete 이진 트리야. 마지막 레벨을 뺀 모든 레벨이 꽉 차 있고 마지막 레벨은 왼쪽부터 차례대로 채워지지. 이 모양에는 빈틈이 없어. 빈틈이 없는 트리는 평평한 배열에 레벨 순서대로 딱 맞아떨어져서 낭비되는 슬롯이 하나도 없고. 그래서 힙에는 노드 객체도 포인터도 전혀 필요 없어. 그냥 Python 리스트고, '트리'라는 건 그 인덱스를 해석하는 방식일 뿐이야.

이동은 전부 산술

이진 트리에서 봤던 그 공식이 여기서 제 몫을 해. 인덱스 i에 있는 원소를 기준으로 보면 이래.

왼쪽 자식은 2i + 1
오른쪽 자식은 2i + 2
부모는 (i − 1) // 2

루트 쪽으로 '트리를 올라가려면' i = (i-1)//2를 반복하면 되고, 내려가려면 두 배 하고 더하면 돼. 포인터를 따라갈 일도, 메모리를 새로 잡을 일도 없어. 트리를 돌아다니는 게 배열 인덱스에 대한 순수한 정수 산술인 거야. 힙 연산이 그렇게 빠른 이유가 정확히 이거고. 구조가 한 줄로 붙어 있으니 CPU 캐시가 계속 따뜻하게 유지되거든. 배열과 연결 리스트에서 배운 게 또 한 번 힘을 발휘하는 순간이야.

complete 이진 트리는 빈틈없이 배열에 들어차. 인덱스 i의 자식은 2i+1과 2i+2, 부모는 (i−1)//2야. 노드도 포인터도 없고 이동이 전부 산술이지. 그리고 메모리가 한 줄로 붙어 있다는 사실이 힙을 캐시 차원에서 빠르게 만들어.

왜 complete를 지켜야 할까

완전성이라는 요구는 장식이 아니야. 배열에 빈틈이 없게 하고 높이를 정확히 ⌊log₂ n⌋으로 붙들어 두는 장치지. 덕분에 모든 힙 연산이 배열 끝, 그러니까 다음 리프 자리나 마지막 리프 자리에서 넣고 빼고, 그다음 원소를 위나 아래로 옮겨 순서를 회복하면 돼. 힙 중간에 구멍이 생기는 걸 허용하면 인덱스 산술이 깨지고 높이도 커질 수 있어. 완전성은 깔끔한 배열 배치와 O(log n) 높이를 동시에 보장해 주는 규율이야.

피파의 고백

아빠가 "힙은 그냥 리스트야"라고 했을 때 안 믿었어. 내 머릿속 힙은 노드와 화살표가 있는 트리였거든. 아빠가 트리 위치에 레벨별로 번호를 매겨서 평평한 배열에 적어보게 하더니, 2i+1이 매번 왼쪽 자식에 정확히 떨어지는 걸 보여줬어. 트리가 사라진 게 아니었어. 알고 보니 처음부터 옷만 갈아입은 배열이었던 거지. 트리라는 개념과 배열이라는 현실이 하나로 합쳐지던 그 순간이, 이 퀘스트 전체에서 내가 제일 좋아하는 '아, 겁먹었던 것보다 단순하네' 순간이야.

Code

인덱스 산술만으로 힙 돌아다니기·python

# 힙은 *이* 리스트야. '트리' 는 인덱스를 읽는 방법일 뿐.
heap = [1, 3, 2, 7, 4, 9, 5]
#  index: 0  1  2  3  4  5  6

def parent(i): return (i - 1) // 2
def left(i):   return 2 * i + 1
def right(i):  return 2 * i + 2

# 트리 구조가 전부 산술에 사는 걸 검증:
i = 0                                  # 루트, 값 1
print("root's children:", heap[left(i)], heap[right(i)])   # 3, 2
j = 4                                  # 값 4
print("4's parent     :", heap[parent(j)])                  # 3

# 리프에서 루트로 정수 산술만으로 오르기 (포인터 없음):
i = 6                                  # 값 5, 리프
path = [heap[i]]
while i > 0:
    i = parent(i)
    path.append(heap[i])
print("leaf-to-root path:", path)      # [5, 2, 1] — 순수 산술 항해

Exercise

배열 기반 힙에서 인덱스 10에 있는 원소를 보자. 두 자식과 부모의 배열 인덱스는 각각 뭘까? 그다음 왜 힙이 새 원소를 자리가 남는 아무 데나가 아니라 반드시 배열 맨 끝, 그러니까 다음 리프 자리에 넣어야 하는지, 안 그러면 뭐가 깨지는지 설명해.

Hint

10의 자식은 2·10+1=21과 22야. 부모는 (10−1)//2 = 4고. 새 원소는 완전성을 지키려고 끝에 들어가야 해. 빈틈이 생기면 안 되거든. 중간에 구멍이 나면 2i+1, 2i+2 인덱스 산술이 깨지고 높이도 log n을 넘어서 커져.

완전성이 배열을 사줘

이동은 전부 산술

왜 complete를 지켜야 할까

피파의 고백

Code

External links

Exercise

Progress

댓글 0