간격 힙(interval heap)에서 최소 요소는 항상 루트 노드의 왼쪽에 위치합니다. 따라서 최솟값 제거(removeMin) 연산은 루트의 왼쪽 요소를 반환하는 것에서 시작되며, 제거 후 힙의 구조적 조건을 유지하기 위해 일련의 재배치 과정이 필요합니다.
기본 제거 절차
- 간격 힙에서 최소 요소는 루트 노드의 왼쪽에 있는 요소입니다. 이 요소를 제거하고 반환합니다.
- 루트 노드 왼쪽에 생긴 빈자리를 채우기 위해, 마지막 노드에서 하나의 요소를 꺼내 다시 루트 노드에 삽입합니다.
- 삽입된 요소는 하위 노드들의 왼쪽 요소들과 순차적으로 비교되며, 간격 힙의 모든 조건이 충족되면 과정이 종료됩니다.
- 비교 도중 어느 단계에서든 노드의 왼쪽 요소가 오른쪽 요소보다 커지면, 두 요소를 서로 교환한 뒤 추가 비교를 계속 진행합니다.
- 모든 과정이 끝나면 루트 노드의 왼쪽에는 다시 최소 요소가 자리하게 됩니다.
removeMin 연산의 세부 동작
위 절차는 힙의 상태에 따라 다음과 같이 세분화하여 설명할 수 있습니다.
- 힙이 비어 있는 경우: 간격 힙에 요소가 없으면 removeMin 연산은 실패합니다.
- 요소가 하나뿐인 경우: 해당 요소를 반환하고, 요소가 없는 빈 간격 힙을 남깁니다.
- 요소가 둘 이상인 경우: 루트의 왼쪽 끝점(left end point)을 반환하며, 이 값을 루트에서 제거합니다.
- 루트가 마지막 노드인 경우: 루트가 곧 간격 힙의 마지막 노드라면 더 이상 수행할 작업이 없습니다.
- 마지막 노드가 루트가 아닌 경우: 마지막 노드에서 왼쪽 값 p를 제거합니다. 이로 인해 마지막 노드가 비게 되면, 해당 노드는 더 이상 힙의 일부로 취급하지 않습니다.
- 재삽입 과정: 마지막 노드에서 제거한 값 p는 루트부터 시작하여 내장된 최소 힙(embedded min heap)에 다시 삽입됩니다.
- 순서 보정: 아래로 내려가는 과정에서 현재 값 p가 검사 중인 노드의 오른쪽 끝점 r보다 작거나 같도록(p ≤ r) 필요하면 p와 r을 교환합니다. 이 재삽입은 일반 힙에 요소를 재삽입할 때 사용하는 것과 동일한 전략으로 수행됩니다.
정리하면, 간격 힙의 최소 요소 제거는 루트의 왼쪽 값을 반환하는 것으로 시작해, 마지막 노드의 값을 루트로 옮긴 뒤 하향식 비교와 필요에 따른 좌우 교환을 통해 힙의 불변 조건을 복원하는 방식으로 완료됩니다.