힙과 우선순위 큐: Heapify부터 구현 선택까지

정렬하지 않고 우선순위를 꺼내는 구조

힙은 완전 이진트리를 배열에 담아 우선순위가 가장 높은 항목을 빠르게 다루는 자료구조다. 대규모 데이터 처리나 스케줄링처럼 다음 작업을 우선순위 기준으로 골라야 하는 상황에서 주로 사용한다.

Min Heap에서는 부모가 자식보다 작거나 같으므로 최솟값이 루트에 놓인다. Max Heap은 반대로 부모가 자식보다 크거나 같고, 최댓값을 루트에서 O(1)에 확인할 수 있다. 삽입과 삭제는 O(log n)이다.

완전 이진트리라는 제약 덕분에 별도 노드 포인터 없이 0-기반 배열 하나로 표현할 수 있다. 인덱스 i의 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2, 부모는 ⌊(i-1)/2⌋로 찾는다. 배열 접근 방식은 포인터 오버헤드를 줄이고 캐시 친화적인 접근에도 유리하다.

Heapify가 힙 속성을 복구하는 방식

Heapify는 특정 위치에서 깨진 힙 속성을 되돌리는 연산이다. 일반적으로 루트 또는 내부 노드에서 시작해 더 높은 우선순위의 자식과 자리를 바꾸며 아래로 내려가는 sift-down을 사용한다.

무정렬 배열을 힙으로 바꾸는 Build-Heap은 마지막 내부 노드부터 앞쪽으로 Heapify를 반복한다. 전체 복잡도는 O(n)이다. 힙 정렬은 여기에 n번의 pop이 더해져 O(n log n)이 된다.

삽입에서는 배열 끝에 항목을 추가한 뒤 sift-up으로 부모와 비교하며 올린다. 삭제에서는 루트를 반환하고 마지막 항목을 루트로 옮긴 다음 sift-down으로 내려보낸다.

동일한 우선순위를 가진 항목의 상대적 순서는 보장되지 않는다. 우선순위는 키 함수나 Comparator로 정하지만, 안정 정렬이 필요한 요구사항은 힙만으로 충족되지 않는다. 표준 힙도 스레드 안전을 보장하지 않으므로 동시 접근에는 외부 락이 필요하다.

Python으로 Min Heap과 Max Heap 다루기

아래 구현은 key로 우선순위를 정의하고 reverse로 Min Heap과 Max Heap을 전환한다. 빈 힙에서 peek 또는 pop을 호출하면 IndexError가 발생한다. 비교할 수 없는 타입을 섞어 넣는 대신 key로 비교 기준을 일관되게 지정해야 한다.

from typing import Callable, Iterable, Optional, TypeVar, List

T = TypeVar("T")

class BinaryHeap:
    def __init__(self, data: Optional[Iterable[T]] = None,
                 key: Optional[Callable[[T], object]] = None,
                 reverse: bool = False):
        """
        key: 우선순위 키 함수. None이면 항목 자체 비교
        reverse=False → Min Heap, True → Max Heap
        """
        self._key = key or (lambda x: x)
        self._sign = -1 if reverse else 1  # sign * cmp로 Max/Min 전환
        self._a: List[T] = list(data) if data is not None else []
        if self._a:
            self._build_heap()

    def __len__(self) -> int:
        return len(self._a)

    def _higher(self, x: T, y: T) -> bool:
        # self._sign=1 → MinHeap: x<y 가 높음, -1 → MaxHeap: x>y 가 높음
        kx = self._key(x); ky = self._key(y)
        if self._sign == 1:
            return kx < ky
        return kx > ky

    def _sift_up(self, i: int) -> None:
        a = self._a
        while i > 0:
            p = (i - 1) // 2
            if self._higher(a[i], a[p]):
                a[i], a[p] = a[p], a[i]
                i = p
            else:
                break

    def _sift_down(self, i: int) -> None:
        a = self._a
        n = len(a)
        while True:
            l = 2 * i + 1
            r = l + 1
            smallest = i
            if l < n and self._higher(a[l], a[smallest]):
                smallest = l
            if r < n and self._higher(a[r], a[smallest]):
                smallest = r
            if smallest != i:
                a[i], a[smallest] = a[smallest], a[i]
                i = smallest
            else:
                break

    def _build_heap(self) -> None:
        # Build-Heap: 마지막 내부 노드부터 sift-down
        for i in range((len(self._a) // 2) - 1, -1, -1):
            self._sift_down(i)

    def push(self, item: T) -> None:
        self._a.append(item)
        self._sift_up(len(self._a) - 1)

    def peek(self) -> T:
        if not self._a:
            raise IndexError("peek from empty heap")
        return self._a[0]

    def pop(self) -> T:
        if not self._a:
            raise IndexError("pop from empty heap")
        a = self._a
        a[0], a[-1] = a[-1], a[0]
        item = a.pop()
        if a:
            self._sift_down(0)
        return item

    def heapify(self, data: Iterable[T]) -> None:
        self._a = list(data)
        self._build_heap()

# 사용 예시
if __name__ == "__main__":
    arr = [5, 3, 8, 1, 2, 7]
    minh = BinaryHeap(arr)               # Min Heap (기본)
    print([minh.pop() for _ in range(len(minh))])  # [1,2,3,5,7,8]

    maxh = BinaryHeap(arr, reverse=True) # Max Heap
    print([maxh.pop() for _ in range(len(maxh))])  # [8,7,5,3,2,1]

    # 객체 + key 사용
    tasks = [{"id":1, "pri":3}, {"id":2, "pri":1}, {"id":3, "pri":2}]
    pq = BinaryHeap(tasks, key=lambda t: t["pri"])  # pri 낮을수록 먼저
    while len(pq):
        print(pq.pop())

Python 표준 라이브러리의 heapq는 Min Heap을 제공한다. Max Heap이 필요하면 키의 부호를 반전하거나 (-key, item) 튜플 패턴을 사용할 수 있다.

Java PriorityQueue에서 비교자 적용하기

Java에서는 PriorityQueue의 기본 동작이 Min Heap이다. Max Heap은 Comparator.reverseOrder()로 구성할 수 있으며, 사용자 타입에는 Comparator를 지정한다. 우선순위를 바꿔야 할 때는 제거 후 수정·재삽입하거나 새 객체를 삽입한다.

import java.util.*;

public class PQDemo {
    public static void main(String[] args) {
        // Min Heap (기본)
        PriorityQueue<Integer> min = new PriorityQueue<>();
        // Max Heap
        PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());

        List<Integer> data = Arrays.asList(5,3,8,1,2,7);

        // O(n) heapify: 컬렉션 생성자 사용
        min.addAll(data);
        max.addAll(data);

        System.out.println(min.peek()); // 1
        while (!max.isEmpty()) System.out.print(max.poll() + " "); // 8 7 5 3 2 1

        // 사용자 타입 + Comparator
        record Task(int id, int pri) {}
        PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingInt(Task::pri));
        pq.addAll(List.of(new Task(1,3), new Task(2,1), new Task(3,2)));
        System.out.println(pq.poll()); // pri=1
    }
}

PriorityQueue 역시 안정 정렬을 보장하지 않는다.

sift-down에서 비교와 교환이 이어지는 경로

⤢✕

자식 인덱스가 배열 범위를 벗어나면 연산을 끝낸다. 같은 우선순위여서 child == i인 경우에는 교환하지 않는다.

구현체의 비용과 선택 기준

구현체	성능(삽입/삭제/조회)	확장성(리사이즈/메모리)	일관성(우선순위 결정)	안정성(스레드)	운영 편의
이진 힙(Binary Heap)	O(log n)/O(log n)/O(1)	동적 배열, 낮은 오버헤드	비교자 기반, 비안정	미보장(외부 락)	광범위한 표준 지원
균형 BST(예: TreeSet)	O(log n)/O(log n)/O(1)	노드 오버헤드 증가	정렬 일관성 양호	미보장(외부 락)	삭제/탐색 유연
피보나치 힙	삽입/감소키 암시적 O(1), 삭제 O(log n)	복잡, 상수 큰 편	이론 최적	구현 복잡	특수 알고리즘용
이항 힙	O(log n)/O(log n)/O(1)	머지 친화	비교자 기반	구현 난이도 중	병합 빈번 시 유리

일반 서비스나 스케줄러에는 이진 힙이 적합하다. 그래프 알고리즘에서 decrease-key가 자주 필요하다면 피보나치 힙이나 페어링 힙을 고려할 수 있지만, 구현 복잡도와의 트레이드오프를 함께 봐야 한다.

스케줄링과 탐색에서의 사용 방식

작업 스케줄링과 Rate Limiting에서는 만료 시간을 기준으로 Min Heap을 두고 지연 큐나 타이머 휠을 보완할 수 있다. 대규모 타이머를 관리할 때 삽입과 삭제를 O(log n)으로 처리해 지연을 줄인다.

Dijkstra와 A*는 open set을 Min Heap으로 유지한다. decrease-key가 필요하면 재삽입 전략을 사용하거나 특수 힙을 선택한다.

스트리밍 중앙값은 Left Max Heap과 Right Min Heap을 함께 두고 균형을 유지하는 방식으로 다룰 수 있다. 상위 K 항목은 크기 K의 Min Heap을 유지해 O(n log K)에 구한다.

이벤트 시뮬레이션에서는 이벤트 시간을 기준으로 Min Heap을 구성한다. 다음 이벤트는 O(1)에 조회하고, 이벤트 삽입과 취소는 O(log n)으로 처리한다.

운영에서 확인할 제약

무정렬 데이터를 Build-Heap으로 초기화하면 O(n)에 시작할 수 있고, 상위 K 문제에서 K≪n이면 O(n log K) 접근이 가능하다. 배열 기반 구조는 포인터 오버헤드를 낮추고 캐시 적중률 개선에 기여한다. 비교자를 정의하면 데이터를 복제하지 않고 재삽입 방식으로 우선순위를 바꿀 수 있다.

0-기반 인덱싱은 언어 관례와 라이브러리 호환성에 맞고, 1-기반 인덱싱은 수식이 단순하다는 장점이 있다. 1-기반 방식은 사용자 정의 구현에서만 추천한다.

멀티스레드 환경에서는 외부 락이나 동시성 컨테이너를 사용한다. 예를 들어 Java의 PriorityBlockingQueue를 사용할 수 있다. 실시간 제약이 있다면 우선순위 역전도 설계 대상이다.

표준 우선순위 큐는 decrease-key를 지원하지 않는 경우가 일반적이므로 remove + insert 패턴을 쓴다. 항목 식별자와 핸들을 매핑해 논리적 키 업데이트를 구현할 수도 있지만, 추가 메모리 비용이 든다. 내부 인덱스를 노출하기보다 lazy deletion의 논리 삭제 플래그를 두고 루트에 도달했을 때 정리하는 전략도 적용할 수 있다.

힙은 O(log n) 연산 비용을 일관되게 제공해 지연 시간을 예측하기 쉽다. 표준 라이브러리를 사용하면 유지보수 비용도 낮출 수 있으며, 요구사항이 커질 때 사용자 정의 힙으로 확장할 수 있다.