간격 힙(Interval Heap)이란?
간격 힙은 완전 이진 트리(complete binary tree)의 한 종류로, 마지막 노드를 제외한 모든 노드가 두 개의 원소를 저장하는 자료구조입니다. 이 자료구조는 최소 힙(Min Heap)과 최대 힙(Max Heap)의 성질을 하나의 트리 안에서 동시에 만족시킬 수 있어, 최솟값과 최댓값을 모두 효율적으로 조회해야 하는 상황에서 유용하게 활용됩니다.
노드와 구간(Closed Interval)의 관계
노드 P에 저장된 두 원소의 우선순위를 각각 'a'와 'b'라고 하고, 항상 a ≤ b를 만족한다고 가정해 봅시다. 이때 노드 P는 닫힌 구간(closed interval) [a, b]를 대표한다고 말합니다.
- a: 노드 P 구간의 좌측 끝점(left endpoint)
- b: 노드 P 구간의 우측 끝점(right endpoint)
두 구간 사이의 포함 관계는 다음과 같이 정의됩니다. 구간 [c, d]가 구간 [a, b]에 포함된다는 것은, 다음 조건을 만족할 때 그리고 그때만 참입니다.
a ≤ c ≤ d ≤ b
부모-자식 노드 간의 포함 규칙
간격 힙에서 가장 중요한 규칙은 부모 노드와 자식 노드 사이의 포함 관계입니다. 임의의 노드 P에 대해, P의 왼쪽 자식과 오른쪽 자식이 나타내는 구간은 반드시 P가 나타내는 구간 안에 포함되어야 합니다. 즉, 루트로 올라갈수록 구간이 넓어지고, 리프 방향으로 내려갈수록 구간이 좁아지는 계층적 구조를 가집니다.
마지막 노드의 예외 처리
트리의 마지막 노드는 원소를 하나만 가질 수 있습니다. 이 경우 해당 원소의 우선순위를 'c'라고 하면, 다음 조건을 만족해야 합니다.
a ≤ c ≤ b
여기서 [a, b]는 마지막 노드의 부모 노드가 나타내는 구간을 의미합니다. 즉, 원소가 하나뿐인 마지막 노드도 부모의 구간 범위 안에 놓이도록 유지됩니다.
최소 힙과 최대 힙의 결합
간격 힙은 본질적으로 최소 힙과 최대 힙이 결합된 형태로 볼 수 있습니다. 모든 노드의 좌측 끝점(a)들을 기준으로 보면 최소 힙의 성질을, 우측 끝점(b)들을 기준으로 보면 최대 힙의 성질을 각각 만족하기 때문입니다.
- 최소 힙 관점: 각 노드의 좌측 끝점은 부모 노드의 좌측 끝점보다 크거나 같으므로, 루트의 좌측 끝점이 전체 트리의 최솟값이 됩니다.
- 최대 힙 관점: 각 노드의 우측 끝점은 부모 노드의 우측 끝점보다 작거나 같으므로, 루트의 우측 끝점이 전체 트리의 최댓값이 됩니다.
이러한 특성 덕분에 간격 힙은 양방향 우선순위 큐(Double-ended Priority Queue)를 구현하는 대표적인 자료구조로 사용되며, 최솟값과 최댓값을 O(1) 시간에 확인할 수 있다는 강력한 장점을 가집니다.