Deap과 Binomial Heap: 양단 조회와 힙 병합의 설계 차이

우선순위 큐에서 조회와 병합은 다른 문제다

최솟값과 최댓값을 모두 즉시 확인해야 하는 큐와, 여러 큐를 반복해서 합쳐야 하는 큐는 같은 힙으로 풀기 어렵다. Deap(Double-ended Heap)은 전자에, Binomial Heap(이항 힙)은 후자에 초점을 둔 구조다.

두 구조 모두 삽입과 삭제에서 O(log n)을 확보한다. 다만 Deap은 최소·최대 키의 즉시 조회를 위해 완전 이진 트리 안에 두 힙을 배치하고, Binomial Heap은 두 힙을 빠르게 합치는 meld를 위해 차수별 트리 포리스트를 유지한다.

Deap은 한 배열에서 최소·최대 영역을 나눈다

Deap의 루트 노드는 비워 둔다. 루트 왼쪽 서브트리는 min-heap, 오른쪽 서브트리는 max-heap으로 두며, 같은 위치에 해당하는 양쪽 노드를 파트너로 연결한다. 왼쪽 값은 대응하는 오른쪽 값보다 작거나 같아야 한다.

최소값은 인덱스 2의 왼쪽 서브트리 루트에서, 최대값은 인덱스 3의 오른쪽 서브트리 루트에서 O(1)에 읽을 수 있다.

⤢✕

점선은 위치 대응, 즉 파트너 관계를 뜻한다. 모든 Lx ≤ Rx 불변식이 유지되어야 한다.

배열 인덱싱에 적합하고, 비워 둔 루트 덕분에 min-heap과 max-heap 영역이 명확히 구분된다. find-min과 find-max는 O(1), 삽입과 삭제는 O(log n)이다. min-max heap보다 비교와 이동 규칙을 단순화하지만 구현 난이도는 중간 수준이다.

대신 Deap에는 직접적인 meld 연산이 없다. 두 Deap을 합치려면 전체 재삽입으로 O(n log n)이 걸리므로, 독립 힙의 빈번한 병합보다는 하나의 큐를 빠르게 조회하는 상황에 맞는다.

Binomial Heap은 차수가 다른 트리를 포리스트로 관리한다

Binomial Heap은 크기가 1, 2, 4, …인 Binomial Tree의 집합으로 구성된다. 각 트리는 힙 속성을 가지며, 같은 차수의 트리 두 개를 연결하면 더 높은 차수의 트리가 된다.

⤢✕

Bk는 k차 Binomial Tree이며 노드 수는 2^k다. 동일 차수의 트리를 합치면 (k+1)차 트리가 생성된다.

루트 리스트는 차수 오름차순으로 정렬한다. meld에서는 두 루트 리스트를 병합 정렬하고, 같은 차수의 트리를 반복적으로 링크한다. 이 전체 과정이 O(log n)이므로 분산 수집이나 스트리밍처럼 부분 힙을 합치는 워크로드에 적합하다.

insert, delete-min, decrease-key의 평균 복잡도는 O(log n)이다. find-min은 루트 리스트를 탐색하면 O(log n)이고, 최소값 보조 포인터를 유지하면 O(1)로 처리할 수 있다. 아몰티즈드 복잡도 분석은 이런 연산의 성능을 일관되게 설명하는 기준이 된다.

삽입과 삭제에서 유지해야 할 불변식

Deap에 값을 삽입할 때는 다음 가용 리프에 값을 놓은 뒤, 반대쪽 같은 위치의 파트너 키와 비교한다. 비교 결과에 따라 min-heap 또는 max-heap 쪽으로 귀속시키고 필요하면 파트너와 교환한다. 이후 해당 힙에서 heapify-up을 수행하므로 삽입은 O(log n)이다.

최소값이나 최대값을 삭제할 때는 대상 루트를 마지막 리프로 보충한다. 파트너 비교로 귀속된 힙을 확인하고 조정한 다음 heapify-down을 실행한다. 필요한 경우 반대편과의 불변식도 다시 확인해야 하며, 이 연산도 O(log n)이다.

파트너 인덱스는 레벨과 오프셋으로 결정된다. 배열 구현에서는 같은 깊이와 오프셋을 반대 서브트리 루트 기준으로 매핑한다.

Binomial Heap의 meld는 두 루트 리스트를 차수 오름차순으로 합치는 것에서 시작한다. 동일 차수 트리 쌍은 힙 속성을 유지하며 링크해 (k+1)차 트리로 만들고, 연속으로 중복된 차수도 처리한다. 시간 복잡도는 O(log n)이다.

삽입은 단일 노드 힙을 만든 뒤 기존 힙과 meld하는 방식이며 아몰티즈드 O(1)~O(log n)이다. delete-min은 최소 루트를 제거하고, 그 자식 서브트리를 역순 루트 리스트의 독립 힙으로 만든 후 원래 힙과 meld한다. 이 과정은 O(log n)이다.

선택 기준은 큐의 운영 형태에 있다

항목	Deap	Binomial Heap
성능	find-min/max O(1), insert/delete O(log n), meld 미지원 수준(O(n log n) 재삽입)	meld O(log n), insert/delete O(log n), find-min O(log n) 또는 O(1) 보조포인터
확장성	단일 힙 대규모 n에서 안정적, 분할/병합 빈번 시 비효율	대규모 분산·스트리밍 합치기 워크로드에 고확장
일관성	파트너 불변식(왼≤오른)로 양단 조회 일관성 확보	차수·힙 속성 유지로 아몰티즈드 일관 성능
안정성	배열 기반 구현 시 캐시 친화, 예측 가능한 로그 시간	루트 리스트/링크 구조로 안정적, 포인터 무결성 중요
운영 편의	단일 큐 고성능 양단 조회에 단순 운용	여러 큐 병합·분할 시 운영 편의 우수, 구현 난이도 중간

실시간 가격 피드에서 최저·최고가를 즉시 읽어야 한다면 Deap이 맞는다. 파티션별 부분 힙을 주기적으로 합치는 배치·스트리밍 로그 집계, 스레드나 노드별 로컬 힙을 글로벌 큐로 합치는 멀티큐 스케줄링에는 Binomial Heap이 어울린다. 제한된 메모리 환경에서 배열 기반 캐시 효율을 중시할 때도 Deap을 고려할 수 있다.

Binomial Heap 구현 예시

표준 Python 3.10+만 사용하는 교육용 간소화 버전이다.

from dataclasses import dataclass
from typing import Optional, Any, List

@dataclass
class Node:
    key: int
    degree: int = 0
    parent: Optional["Node"] = None
    child: Optional["Node"] = None
    sibling: Optional["Node"] = None

def link_tree(y: Node, z: Node) -> Node:
    # 가정: y.key >= z.key, 동일 차수
    y.parent = z
    y.sibling = z.child
    z.child = y
    z.degree += 1
    return z

def merge_root_lists(h1: Optional[Node], h2: Optional[Node]) -> Optional[Node]:
    # 차수 기준 병합
    head = tail = None
    while h1 or h2:
        pick_h1 = (h2 is None) or (h1 and h1.degree <= h2.degree)
        node = h1 if pick_h1 else h2
        if pick_h1: h1 = h1.sibling
        else: h2 = h2.sibling
        if tail:
            tail.sibling = node
            tail = node
        else:
            head = tail = node
    return head

def union(h: Optional[Node]) -> Optional[Node]:
    if not h or not h.sibling: return h
    prev = None
    curr = h
    next_ = h.sibling
    while next_:
        if (curr.degree != next_.degree) or (next_.sibling and next_.sibling.degree == curr.degree):
            prev, curr, next_ = curr, next_, next_.sibling
        else:
            # 차수 동일, 키 작은 쪽이 루트 유지
            if curr.key <= next_.key:
                curr.sibling = next_.sibling
                curr = link_tree(next_, curr)
                next_ = curr.sibling
            else:
                if prev: prev.sibling = next_
                else: h = next_
                curr = link_tree(curr, next_)
                next_ = curr.sibling
    return h

class BinomialHeap:
    def __init__(self):
        self.head: Optional[Node] = None

    def meld(self, other: "BinomialHeap"):
        self.head = union(merge_root_lists(self.head, other.head))
        other.head = None

    def insert(self, key: int):
        tmp = BinomialHeap()
        tmp.head = Node(key)
        self.meld(tmp)

    def find_min(self) -> Optional[int]:
        if not self.head: return None
        y = None
        x = self.head
        min_key = float("inf")
        while x:
            if x.key < min_key:
                min_key = x.key
                y = x
            x = x.sibling
        return y.key if y else None

    def delete_min(self) -> Optional[int]:
        if not self.head: return None
        # 최소 루트 분리
        prev_min = None
        min_node = self.head
        prev = None
        curr = self.head
        min_key = curr.key
        while curr:
            if curr.key < min_key:
                min_key = curr.key
                prev_min = prev
                min_node = curr
            prev = curr
            curr = curr.sibling
        # 리스트에서 제거
        if prev_min: prev_min.sibling = min_node.sibling
        else: self.head = min_node.sibling
        # 자식 역순 루트 리스트 생성
        child = min_node.child
        rev_head = None
        while child:
            nxt = child.sibling
            child.parent = None
            child.sibling = rev_head
            rev_head = child
            child = nxt
        # 병합
        other = BinomialHeap()
        other.head = rev_head
        self.meld(other)
        return min_key

merge_root_lists가 루트 리스트를 차수 기준으로 합친 뒤, union이 동일 차수의 트리를 링크한다. 이 구현에서 find_min과 delete_min은 O(log n)을 보장한다.

Deap 구현 시 배열에서 처리할 흐름

insert(x)는 배열 끝에 값을 배치하고 파트너와 비교한 뒤, 귀속할 힙을 정해 그쪽에서 sift-up을 수행한다.

delete-min은 왼쪽 루트를 제거하고 마지막 리프를 이동한 다음 파트너 규칙을 보정하고 min-heap sift-down을 수행한다.

배열 인덱스 기반 파트너 계산은 레벨 k에서 오프셋 o를 반대 서브트리 루트 기준의 같은 o 위치로 매핑하는 방식이다. 구현에서는 레벨별 시작 인덱스인 precomputed 2^k를 사용할 수 있다.

워크로드에 따라 기대할 수 있는 변화

상시 양단 탐색이 전체 요청의 30% 이상인 워크로드에서는 Deap의 min/max O(1) 조회로 평균 응답시간 20~40% 단축을 기대할 수 있다.

N개의 부분 힙을 합치는 Binomial Heap은 비용 O(N log n)으로 처리하며, 재삽입 O(N·log n) 대안과 비교해 약 1.5~3배 속도 개선을 기대할 수 있다. Deap은 배열 기반 구현을 통해 캐시 적중률 향상과 파편화 감소를 노릴 수 있다.

샤딩, 병합, 스냅샷 복구가 반복되는 환경에서는 Binomial Heap의 단순한 meld가 운영 복잡도를 낮춘다. 양단 즉시 조회의 비중이 크면 Deap, 다중 힙 병합이 잦으면 Binomial Heap이 선택 기준이 된다.