간격 힙은 각 노드에 두 개의 요소가 포함된 포함된 최소-최대 힙과 동일합니다. 이것은 완전한 이진 트리로 정의됩니다.
- 왼쪽 요소가 오른쪽 요소보다 작거나 같습니다.
- 두 요소 모두 닫힌 간격을 정의합니다.
- 루트 이외의 노드가 나타내는 간격은 상위 노드의 하위 간격입니다.
- 왼쪽의 요소는 최소 힙을 나타냅니다.
- 오른쪽에 있는 요소는 최대 힙을 나타냅니다.
요소 수에 따라 두 가지 경우가 허용됩니다. -
- 짝수 요소:이 경우 각 노드에는 a ≤ b인 a 및 b라는 두 개의 요소가 포함됩니다. 모든 노드는 간격 [a, b]로 표시됩니다.
- 홀수개의 요소:이 경우 마지막 노드를 제외한 각 노드는 간격 [a, b]로 표시되는 두 개의 요소를 포함하는 반면 마지막 노드는 단일 요소를 포함하고 간격 [a, b]로 표시됩니다. .
간격 힙은 일반 힙을 초기화하는 데 사용된 것과 동일한 전략을 구현하여 초기화될 수 있습니다. 각 하위 트리가 간격 힙으로 표시되도록 힙 하단에서 루트로 작업합니다. 각 하위 트리에 대해 먼저 루트의 요소를 정렬합니다. 그런 다음 removeMin 함수에 사용된 재삽입 전략을 구현하는 이 하위 트리 루트의 왼쪽 끝점을 다시 삽입하고 removeMax 함수에 사용된 전략을 구현하는 이 하위 트리 루트의 오른쪽 끝점을 다시 삽입합니다.