간격 힙(interval heap)은 각 노드가 두 개의 원소를 저장하는 임베디드 min-max 힙(embedded min-max heap)과 동일한 자료구조입니다. 간격 힙은 완전 이진 트리(complete binary tree)로 정의되며, 다음과 같은 성질을 만족해야 합니다.
- 왼쪽 원소는 오른쪽 원소보다 작거나 같습니다.
- 두 원소는 하나의 닫힌 구간(closed interval)을 정의합니다.
- 루트를 제외한 모든 노드가 나타내는 구간은 부모 노드 구간의 부분 구간(sub-interval)입니다.
- 왼쪽에 위치한 원소들은 최소 힙(min heap) 구조를 이룹니다.
- 오른쪽에 위치한 원소들은 최대 힙(max heap) 구조를 이룹니다.
원소 개수에 따른 두 가지 경우
노드에 저장된 원소의 개수에 따라 다음 두 가지 경우가 허용됩니다.
1. 짝수 개의 원소
이 경우 각 노드는 a와 b(a ≤ b)라는 두 개의 원소를 포함하며, 모든 노드는 구간 [a, b]로 표현됩니다.
2. 홀수 개의 원소
이 경우 마지막 노드를 제외한 모든 노드는 구간 [a, b]로 표현되는 두 개의 원소를 포함합니다. 마지막 노드에는 원소가 하나만 존재하며, 이 노드 역시 구간 형태([a, a])로 표현됩니다.
간격 힙 초기화 방법
간격 힙은 일반 힙(heap)을 초기화할 때 사용하는 것과 동일한 전략으로 초기화할 수 있습니다. 즉, 힙의 가장 아래쪽(리프 방향)에서 루트 방향으로 올라가면서, 각 서브트리(subtree)가 올바른 간격 힙이 되도록 만드는 방식입니다.
각 서브트리에 대해 수행하는 절차는 다음과 같습니다.
- 루트 원소 정렬: 먼저 해당 서브트리 루트에 있는 두 원소를 순서대로 정렬하여 왼쪽 원소가 오른쪽 원소보다 작거나 같게 만듭니다.
- 왼쪽 끝점 재삽입: removeMin 함수에서 사용하는 재삽입(reinsertion) 전략을 적용하여 루트의 왼쪽 끝점(left endpoint)을 다시 삽입합니다.
- 오른쪽 끝점 재삽입: removeMax 함수에서 사용하는 전략을 적용하여 루트의 오른쪽 끝점(right endpoint)을 다시 삽입합니다.
이 과정을 모든 서브트리에 대해 반복하면 전체 트리가 유효한 간격 힙으로 초기화됩니다.