힙에서 원소 삭제하기

일단 힙에서는 가장 큰 원소만 삭제할 수 있습니다. 다른 원소에는 직접 접근할 수 없기 때문입니다. 최대 원소는 항상 트리의 루트에 존재하므로, 루트 노드를 삭제해야 합니다. 루트를 삭제할 경우, 어느 노드를 이용하여 루트를 대체할 것인지를 결정해야 합니다. 이를 위해 먼저 루트 노드와 트리의 맨 마지막 노드를 서로 교환한 후, 마지막 노드를 삭제합니다. 이렇게 하면 최대 원소를 삭제한 것이 되며, 다만 루트 위치에서 부모 노드가 자식 노드보다 커야 한다는 불변성을 만족하지 못하게 됩니다. 이 문제를 해결하기 위해 루트 노드와 두 자식 노드를 서로 비교하여 그중 더 큰 노드와 서로 교환합니다. 이제 루트 노드의 두 서브 트리 중 하나에 대해 불변 규칙이 깨진 상태가 되었을 것입니다. 그러므로 서브 트리에 대해서도 노드 교환 작업을 재귀적으로 반복합니다. 이러한 방식으로 불변성을 만족하지 못하는 위치가 점차 트리 아래쪽으로 이동하게 됩니다. 교환 작업의 최대 횟수는 트리의 높이와 같으므로 원소 삭제의 시간 복잡도는 O(log N)으로 표현할 수 있습니다. 이러한 원소 삭제 과정을 그림 2-17에 나타냈습니다.

▲ 그림 2-17 힙에서 원소 삭제하기