간격 힙(interval heap)에 새로운 요소를 삽입할 때는 힙에 현재 존재하는 요소의 개수에 따라 두 가지 경우로 나누어 처리합니다.
요소 개수가 홀수인 경우
간격 힙에 저장된 요소의 개수가 홀수라면, 새로운 요소는 우선 마지막 노드에 삽입됩니다. 이후 이 요소는 앞선 노드들의 요소들과 순차적으로 비교되면서, 간격 힙이 반드시 만족해야 하는 조건들을 검사받습니다. 만약 해당 요소가 어떤 조건도 충족하지 못한다면, 모든 조건을 만족할 때까지 마지막 노드에서 루트(root) 방향으로 요소가 이동됩니다.
요소 개수가 짝수인 경우
요소의 개수가 짝수라면, 새로운 요소를 삽입하기 위해 먼저 추가 노드를 하나 생성합니다. 이때 새 요소가 부모 노드 구간의 왼쪽에 속한다면 최소 힙(min heap) 부분으로 처리되고, 부모 구간의 오른쪽에 속한다면 최대 힙(max heap) 부분으로 처리됩니다.
그다음에는 요소를 순차적으로 비교하면서, 간격 힙의 모든 조건이 충족될 때까지 마지막 노드에서 루트 방향으로 이동시킵니다. 반면, 새 요소가 부모 노드의 구간 내부에 이미 포함되어 있다면 그 자리에서 즉시 삽입 과정이 종료되며, 별도의 요소 이동은 발생하지 않습니다.
삽입 연산의 시간 복잡도
요소 삽입에 소요되는 시간은 모든 조건을 만족시키기 위해 필요한 이동 횟수에 좌우되며, 전체 시간 복잡도는 O(log n)입니다.