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

"힙은 종이에선 트리지만 메모리에선 배열이야. 노드 객체 없음, left/right 포인터 없음 — 그냥 산술. 그게 '트리' 가 네가 쓸 가장 빠른 구조 중 하나일 수 있는 비밀이야."

완전성이 배열을 사줘

이진 힙은 늘 complete 이진 트리야: 마지막 빼고 모든 레벨이 꽉 차고, 마지막은 엄격히 왼쪽에서 오른쪽으로 채워져. 그 모양엔 빈틈이 없어 — 빈틈 없는 트리는 평평한 배열에 레벨별로 완벽히 매핑돼, 낭비 슬롯 제로. 그래서 힙은 노드 객체나 포인터가 전혀 필요 없어. 그냥 Python 리스트고, '트리' 는 인덱스를 해석하는 방법이야.

항해는 그냥 산술

이진-트리 lesson 의 그 공식이, 이제 값을 해. 인덱스 i 의 원소에 대해:

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

루트로 '트리를 오르려면', i = (i-1)//2 를 계속 해. 내려가려면, 두 배 하고 더해. 포인터 역참조 없음, 할당 없음 — 트리를 돌아다니는 게 배열 인덱스의 순수 정수 산술이야. 정확히 힙 연산이 그렇게 빠른 이유야: 구조가 연속이라, CPU 캐시가 따뜻하게 유지돼 (배열-vs-연결-리스트 lesson, 또 값을 함).

complete 이진 트리는 빈틈없이 배열에 패킹돼: 인덱스 i 의 자식은 2i+1 / 2i+2, 부모는 (i−1)//2. 노드 없음, 포인터 없음 — 항해는 산술이고, 연속 배치가 힙을 캐시-빠르게 만들어.

왜 complete 로 유지돼야 하나

완전성 요구는 장식이 아니라 — 배열을 빈틈없게, 높이를 정확히 ⌊log₂ n⌋ 으로 유지하는 거야. 그래서 모든 힙 연산이 배열 끝 (다음/마지막 리프 위치) 에 추가하거나 거기서 제거하고, 그다음 원소를 위나 아래로 옮겨 순서를 회복해. 힙에 구멍이 허용되면, 인덱스 산술이 깨지고 높이가 커질 수 있어. 완전성이 깔끔한 배열 패킹이랑 모든 걸 빠르게 하는 O(log n) 높이 둘 다 보장하는 규율이야.

피파의 고백

아빠가 "힙은 그냥 리스트야" 라고 했을 때, 안 믿었어 — 난 그걸 노드랑 화살표 있는 트리로 그렸거든. 아빠가 트리 위치를 레벨별로 번호 매겨 평평한 배열에 쓰게 하고, 2i+1 이 늘 왼쪽 자식에 착지하는 걸 보여줬어. 트리가 사라진 게 아니라; 알고 보니 내내 의상 입은 배열이었어. 그 붕괴 — 트리 개념, 배열 현실 — 가 DSA 전체에서 내가 제일 좋아하는 '오, 두려워한 것보다 단순했네' 순간 중 하나야.

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