간격 힙(Interval Heap)이란?
양단 우선순위 큐(Double-Ended Priority Queue, DEPQ), 흔히 간격 힙(interval heap)이라고 불리는 자료구조는 최소 우선순위 요소와 최대 우선순위 요소를 모두 효율적으로 조회하고 삭제할 수 있는 힙 기반 구조입니다. 일반적인 최소 힙이나 최대 힙과 달리, 양쪽 끝에서 동시에 우선순위를 다룰 수 있다는 점이 가장 큰 특징입니다.
간격 힙에서 지원하는 대표적인 연산은 다음과 같습니다.
간격 힙의 주요 연산
isEmpty()
DEPQ가 비어 있는지 확인하는 함수로, 큐가 비어 있으면 true를 반환합니다.
size()
DEPQ에 현재 저장되어 있는 전체 요소의 개수를 반환합니다.
getMin()
가장 낮은 우선순위를 가진 요소를 반환합니다.
getMax()
가장 높은 우선순위를 가진 요소를 반환합니다.
put(z)
새로운 요소 z를 DEPQ에 삽입합니다.
removeMin()
우선순위가 가장 낮은 요소를 제거한 뒤, 해당 요소를 반환합니다.
removeMax()
우선순위가 가장 높은 요소를 제거한 뒤, 해당 요소를 반환합니다.
연산별 시간 복잡도
간격 힙의 각 연산은 아래와 같은 시간 복잡도를 가집니다.
- isEmpty(), size(), getMin(), getMax() — 네 가지 연산 모두 O(1)의 상수 시간이 소요됩니다.
- put(z), removeMin(), removeMax() — 삽입과 삭제 연산은 힙 재구성 과정이 필요하기 때문에 각각 O(log n)의 로그 시간이 소요됩니다.
- n개 요소 초기화 — n개의 요소로 간격 힙을 초기화(힙 생성)하는 데는 O(n)의 선형 시간이 걸립니다.
정리하면, 단순 조회 성격의 연산은 상수 시간에 처리되고, 삽입·삭제 연산은 트리의 높이에 비례하는 로그 시간 안에 완료됩니다. 이처럼 균형 잡힌 성능을 보이기 때문에 간격 힙은 최솟값과 최댓값을 반복적으로 함께 다루어야 하는 스케줄링, 이중 우선순위 처리 등의 문제에서 유용하게 활용됩니다.