완전이진트리와 배열 기반 힙 구현

배열에 담기는 트리의 형태

완전이진트리는 높이 h인 트리에서 0..h-1 레벨이 모두 채워지고, h 레벨의 노드가 왼쪽에서 오른쪽으로 빈틈없이 배치되는 이진트리다. 마지막 레벨만 일부 채워질 수 있으며, 높이 h에서 노드 수 n은 2^h ≤ n ≤ 2^(h+1)-1 범위에 놓인다.

이 형태는 힙의 기반이 된다. 최대 힙과 최소 힙은 완전이진트리의 형태 속성 위에 키 순서 규칙을 더한 자료구조다. 트리 모양을 따로 유지할 필요가 없다는 점이 배열 구현의 핵심이다.

1-기반 인덱스를 쓰면 부모는 i/2, 왼쪽 자식은 2i, 오른쪽 자식은 2i+1로 찾을 수 있다. 포인터 연결 없이 연속 메모리에 노드를 둘 수 있으므로, 상향 이동과 하향 이동도 인덱스 계산만으로 처리한다.

힙 연산을 지탱하는 구조적 특성

삽입과 삭제로 구조가 바뀌는 위치는 마지막 레벨의 끝단이다. 좌측 정렬과 레벨 순서가 유지되므로 배열 길이와 마지막 인덱스 위치만으로 형태의 유효성을 확인할 수 있다.

연속 메모리 배치는 캐시 지역성에도 영향을 준다. 포인터를 따라가는 간접 접근이 없고, 인덱스 연산으로 부모·자식 노드를 오가므로 분기와 간접 접근을 줄일 수 있다. 반면 단일 배열의 용량이 부족해지면 전체 복사가 필요한 재할당이 발생할 수 있으므로 성장 정책은 별도로 설계해야 한다.

힙을 처음 만들 때는 배열을 하향 힙화하는 Floyd 방식으로 O(n)에 구축할 수 있다. 대량 초기화에 적합하며, 레벨 순서 기반 직렬화와 역직렬화도 단순해진다.

우선순위가 계속 바뀌는 곳에서의 사용

스케줄러, 이벤트 루프, 타임아웃 관리에서는 최솟값이나 최댓값에 바로 접근하면서 항목을 계속 넣고 빼야 한다. 힙 기반 우선순위 큐는 이 요구를 처리한다. 경로 탐색의 Dijkstra와 A*, 네트워크 패킷 처리, 작업 대기열 관리에서도 같은 구조가 쓰인다.

정렬과 스트리밍 처리에도 연결된다. 힙 정렬은 제자리 정렬로 O(n log n) 시간과 O(1) 추가 메모리를 사용한다. 스트리밍 데이터에서는 Min/Max-Heap 조합으로 Top-K와 Median 같은 통계량을 유지할 수 있다.

포인터 비용이 부담되는 임베디드 환경이나 커널 공간에서는 예측 가능한 메모리 풋프린트가 장점이 된다.

삽입과 삭제에서 지켜야 할 조건

새 키 k를 넣을 때는 배열 끝에 추가한 뒤 부모와 비교하며 상향 힙화를 수행한다. 삭제에서는 마지막 원소를 루트로 옮기고 자식과 비교하며 하향 힙화를 적용한다. 두 과정 모두 힙 순서와 완전이진트리 형태를 함께 보존해야 한다.

용량이 부족하면 리사이즈가 필요하고, 비교할 수 없는 타입을 넣으면 예외 처리가 필요하다. 동시성 환경에서는 락이나 원자적 스왑을 적용한다.

⤢✕

최소 힙을 배열로 구현하기

다음 구현은 Python 3.10+와 1-기반 인덱스를 전제로 한 최소 힙이다.

# python 3.10+
class MinHeap:
    def __init__(self, data=None):
        self.a = [None]
        if data:
            self.a += data[:]  # 1-기반
            self._build()

    def _swap(self, i, j):
        self.a[i], self.a[j] = self.a[j], self.a[i]

    def _up(self, i):
        while i > 1 and self.a[i] < self.a[i // 2]:
            self._swap(i, i // 2)
            i //= 2

    def _down(self, i):
        n = len(self.a) - 1
        while 2 * i <= n:
            j = 2 * i
            if j + 1 <= n and self.a[j + 1] < self.a[j]:
                j += 1
            if not (self.a[j] < self.a[i]):
                break
            self._swap(i, j)
            i = j

    def _build(self):
        for i in range((len(self.a) - 1) // 2, 0, -1):
            self._down(i)

    def push(self, x):
        self.a.append(x)
        self._up(len(self.a) - 1)

    def pop(self):
        if len(self.a) == 1:
            raise IndexError("empty heap")
        n = len(self.a) - 1
        self._swap(1, n)
        v = self.a.pop()
        if len(self.a) > 1:
            self._down(1)
        return v

    def peek(self):
        if len(self.a) == 1:
            raise IndexError("empty heap")
        return self.a[1]

# 사용 예
h = MinHeap([5,3,8,4,1])
print(h.peek())  # 1
h.push(0)
print(h.pop())   # 0

이 구현에서 push와 pop은 O(log n), peek은 O(1), build는 O(n)이다.

포인터 이진트리와 선택 기준

항목	배열 기반 완전이진트리(힙)	포인터 기반 일반 이진트리
성능	인덱스 연산·캐시 친화, 힙 연산 O(log n)	포인터 추적 비용, 불균형 시 최악 O(n)
확장성	동적 배열 리사이즈 필요, 선형 복사 오버헤드	노드 단위 확장 용이, 할당자 성능 의존
일관성	형태 제약 간단 검증(길이/인덱스)	구조 불변식 검증 비용 상대 높음
안정성	파편화 낮음, 연속 메모리 의존	파편화 가능, 개별 노드 실패 전파 낮음
운영 편의	직렬화/역직렬화 용이, 파일 매핑 친화	구조 유연, 삽입 위치 다양

성능과 운영에서 남는 차이

삽입과 삭제는 O(log n), 최솟값·최댓값 조회는 O(1)로 처리되며, 대량 초기화는 O(n) 하향 힙화로 구축할 수 있다. 캐시 적중률 향상에 따라 실측 1.2~2.0배 처리량 향상 사례도 보고됐다(플랫폼·데이터 분포에 따라 상이, 최신 정보 확인 필요).

포인터 필드가 없으므로 노드별 오버헤드도 줄어든다. 64비트 환경에서는 포인터 2개 절감 ≈ 노드당 16바이트 절약이 가능하다. n=1,000,000 노드라면 대략 16MB를 절감할 수 있다(부가 메타데이터 제외, 구현에 따라 상이).

직렬화, 스냅샷, 메모리맵 파일(MMAP)과 결합하기 쉽고 상태 점검과 복구 절차도 단순해진다. 동시성 환경에서는 파인 그레인 락 대신 힙 단일 락으로도 충분한 처리율을 달성할 수 있으며, 대안으로 락-프리 다중 힙 샤딩 전략을 적용할 수 있다. 대용량·실시간 시스템에서는 리사이즈 정책, 동시성 제어, 직렬화 포맷까지 함께 설계해야 한다.