최소-최대히프·디프·이항히프로 보는 우선순위 큐 선택

극값 조회와 합병 요구가 힙 선택을 가른다

우선순위 큐가 최솟값만 꺼내면 되는지, 최솟값과 최댓값을 함께 즉시 확인해야 하는지, 여러 큐를 반복해서 합쳐야 하는지에 따라 적합한 힙 구조가 달라진다. 최소-최대히프, 디프, 이항히프는 각각 이중 우선순위 처리와 합병 성능에서 다른 균형점을 만든다.

최소-최대히프는 배열 기반 완전이진트리에서 레벨마다 Min 힙과 Max 힙 불변식을 교대로 적용한다. 루트 레벨은 최소를 담당하고 다음 레벨은 최대를 담당하며 이 패턴이 계속 이어진다. 최솟값은 O(1), 최댓값은 루트 자식을 비교해 O(1)에 찾을 수 있다. 삽입과 삭제는 O(log n)이며, 합병을 위한 별도 최적화는 없다.

디프(Deap)는 하나의 배열을 Min-heap 파티션과 Max-heap 파티션으로 나누고, 두 파티션의 대응 노드를 매핑한다. 이 매핑으로 모든 Min 값이 모든 Max 값보다 작거나 같은 전역 불변식을 유지한다. 최솟값·최댓값 조회는 O(1), 삽입·삭제는 O(log n)이다. 반면 합병은 일반적으로 지원이 미흡하며 O(n) 재구성이 필요하다.

이항히프는 차수가 겹치지 않는 이항트리 포레스트를 포인터로 연결한 구조다. 차수 0, 1, 2 등의 트리가 각각 0개 또는 1개만 존재하도록 관리한다. 최소 루트 포인터가 있으면 find-min은 O(1)이며, insert와 union(external meld)은 O(log n), extract-min과 decrease-key도 O(log n)이다. 다만 최댓값까지 함께 조회하는 이중 우선순위 요구에는 맞지 않는다.

구조가 유지하는 불변식과 비용

최소-최대히프에서는 짝수 레벨이 최소 힙, 홀수 레벨이 최대 힙의 역할을 맡는다. 삽입할 때는 새 원소의 레벨을 판정한 뒤 min 또는 max 방향으로 버블업한다. find-min/max는 O(1), delete-min/max는 O(log n)이다. 배열 구조여서 인덱스 계산이 단순하고 캐시 지역성이 좋으며, 두 힙을 따로 두는 방식보다 메모리를 절약할 수 있다.

디프는 루트를 제외한 좌측에 Min-heap, 우측에 Max-heap을 둔다. 삽입 시에는 어느 파티션에 들어갈지 판단하고 대응 노드와 비교·교환한 뒤 해당 파티션을 힙화한다. 삭제는 루트를 교체한 뒤 각 파티션에서 힙다운한다. 포인터 없이 단일 배열을 사용하므로 메모리와 상수계수 측면에서 유리할 수 있지만, 대응 인덱스 매핑 로직은 구현 난도를 높인다.

이항히프의 각 이항트리는 2^k개의 노드를 가진다. 두 힙을 합칠 때는 루트 리스트를 차수 순으로 병합하고, 동일 차수 트리가 나타나면 캐리 전파처럼 결합해 차수 중복을 없앤다. 이 과정 때문에 멜드가 빈번한 상황에서 강점이 생긴다. 대신 포인터 기반 구조이므로 메모리 오버헤드와 구현 복잡도가 따른다.

요구사항에서 선택으로 이어지는 흐름

⤢✕

양방향으로 극값을 즉시 읽어야 하고 멜드가 드물다면 최소-최대히프 또는 디프가 출발점이다. 이때 메모리와 상수계수에 민감한 환경에서는 디프를 우선 검토할 수 있다.

반대로 단일 방향 우선순위 큐를 여러 개 합치는 일이 잦다면 이항히프가 맞는다. 멜드가 드물고 한쪽 극값만 필요하면 일반 이진 힙이 더 단순하고 효율적인 선택이 될 수 있다.

구조	주요 연산	합병	불변식	시간복잡도	운영 특성
최소-최대히프	find-min/max O(1), insert/delete O(log n)	전용 지원 없음, 보통 O(n) 재구성	교대 레벨 Min/Max 불변식	전 연산 최악 O(log n)	배열 기반, 구현 중간 난이도, 라이브러리 드묾
디프	find-min/max O(1), insert/delete O(log n)	일반적으로 미지원, O(n) 수준	Min 파티션 ≤ Max 파티션 전역 불변식	전 연산 최악 O(log n)	배열 기반, 매핑 로직 난이도↑, 메모리 효율
이항히프	find-min O(1, 포인터), insert/union O(log n), extract-min O(log n)	강점: union O(log n)	각 트리 이항 성질·차수 중복 금지	최악 보장 O(log n), 분할상환 불필요	포인터 구조 복잡, 구현 난이도↑, 일부 라이브러리 존재

이항히프의 find-min은 최소 루트 포인터를 유지할 때 O(1)이다. 포인터를 유지하지 않으면 루트 스캔에 O(log n)이 든다.

작업 부하에 따른 사용 위치

최소-최대히프는 최대 지연으로 SLA 위반을 감지하면서 최소 지연으로 SLA 준수 여부도 확인해야 하는 환경에 쓸 수 있다. 주문서(Book)의 상단·하단 가격을 즉시 읽거나, 게임 매칭에서 상·하위 레이팅을 함께 관리하는 경우도 같은 성격이다.

디프는 임베디드나 캐시 제약처럼 메모리와 상수계수에 민감하면서 이중 우선순위가 필요한 환경에 맞는다. 두 힙을 동기화하는 대신 단일 배열을 유지하므로 데이터 복제를 없애고 운영 복잡도를 줄일 수 있다.

이항히프는 멀티큐 스케줄러나 분산 태스크 통합처럼 여러 작업 큐를 주기적으로 합치는 멜드-집약 워크로드에 적합하다. 외부 소스를 단계적으로 병합하는 ETL·스케줄링 파이프라인도 해당한다.

기대할 수 있는 효과와 감수할 비용

이중 힙을 2개 두는 방식과 비교하면 최소-최대히프와 디프는 원소 중복 저장을 제거해 메모리를 최대 약 50% 절감한다. find-min/max O(1)은 극값 조회 지연을 최소화하며, 캐시 지역성이 좋아지는 환경에서는 디프가 상수계수 관점에서 10~30% 개선될 수 있다. 이 수치는 환경에 의존한다.

멜드가 자주 발생하면 이항히프의 union O(log n)은 총 처리 시간을 크게 줄일 수 있다. 큐 수가 증가할 때 선형 비용 대신 로그 보상을 기대할 수 있기 때문이다.

운영에서는 동시성 제어와 임의 원소 처리를 별도로 검토해야 한다. 최소-최대히프와 디프는 단일 컨테이너여서 전체 락 범위를 단순화할 수 있지만, 경합이 높으면 분할 샤딩과 워크 스틸링을 고려한다. 이항히프는 루트 리스트 단위로 락을 나누는 방식이 권장된다.

임의 원소 삭제나 decrease-key가 잦다면 인덱스 맵(핸들)을 유지해야 한다. 이항히프의 decrease-key는 O(log n)으로 안정적이지만, 최소-최대히프와 디프에서는 추가 인덱싱 오버헤드가 생긴다. 멜드가 드문 상황에서는 이항히프의 포인터 오버헤드가 손해가 될 수 있고, 멜드가 상시 발생한다면 이항히프를 우선 선택할 이유가 생긴다.