- 간격 힙에서 가장 작은 요소는 루트 노드의 왼쪽에 있는 요소입니다. 이 요소는 제거되고 반환됩니다.
- 루트 노드의 왼쪽에 생성된 공백을 채우기 위해 마지막 노드의 요소를 제거하고 루트 노드에 다시 삽입합니다.
- 이 요소는 다음으로 내림차순 노드의 모든 왼쪽 요소와 연속적으로 비교되며 간격 힙에 대한 모든 조건이 충족되면 프로세스가 종료됩니다.
- 어떤 단계에서든 노드의 왼쪽 요소가 오른쪽 요소보다 높아지면 두 요소를 교환하여 추가 비교를 수행합니다.
- 마침내 루트 노드는 다시 왼쪽에 있는 가장 작은 요소를 포함하게 됩니다.
이 절차는 다음과 같이 설명할 수도 있습니다. -
최소 요소 제거는 여러 가지 방법으로 처리됩니다. -
- 간격 힙이 비어 있으면 removeMin 작업이 실패합니다.
- 간격 힙에 요소가 하나만 있는 경우 이 요소를 반환해야 합니다. 요소 없이 간격 힙을 남깁니다.
- 요소가 두 개 이상인 경우 루트의 왼쪽 끝점이 반환되어야 합니다. 이 점은 루트에서 제거됩니다.
- 루트가 간격 힙의 마지막 노드를 나타내는 경우 더 이상 수행할 작업이 없습니다.
- 마지막 노드가 루트 노드가 아닌 경우 마지막 노드에서 왼쪽 점 p를 제거합니다. 이로 인해 마지막 노드가 비어 있게 되면 마지막 노드는 더 이상 힙의 일부가 아닙니다.
- 마지막 노드에서 제거된 점 p는 루트에서 시작하여 포함된 최소 힙에 다시 삽입됩니다.
- 아래로 이동함에 따라 현재 p를 검사 중인 노드의 오른쪽 끝점 r과 교환하여 p ≤r이 되도록 해야 할 수 있습니다. 재삽입은 일반 힙에 다시 삽입하는 데 사용된 것과 동일한 전략을 구현하여 수행됩니다.