최대 힙(Max Heap)에서 요소 삭제하기 – 알고리즘과 예제

이번 글에서는 이진 최대 힙(Binary Max Heap) 자료구조에서 요소를 삭제하는 방법을 살펴보겠습니다. 최대 힙은 부모 노드가 항상 자식 노드보다 크거나 같은 값을 가지는 완전 이진 트리로, 삭제 연산은 주로 루트(최댓값)를 제거할 때 사용됩니다.

아래와 같은 초기 트리가 있다고 가정해 보겠습니다.

삭제 알고리즘

delete(heap, n) −
Begin
    if heap is empty, then exit
    else
        item := heap[1]
        last := heap[n]
        n := n – 1
        for i := 1, j := 2, j <= n, set i := j and j := j * 2, do
            if j < n, then
                if heap[j] < heap[j + 1], then j := j + 1
            end if
            if last >= heap[j], then break
            heap[i] := heap[j]
        done
    end if
    heap[i] := last
End

알고리즘 동작 원리

위 의사코드의 핵심 흐름은 다음과 같습니다.

1. 루트 값 저장: 삭제할 값인 루트 노드(heap[1])를 item에 임시로 저장합니다.
2. 마지막 요소 이동: 힙의 마지막 요소(heap[n])를 꺼내어 힙 크기를 하나 줄인 뒤, 루트 위치에 대신 놓습니다.
3. 재정렬(Sift-down): 루트에 옮겨진 값이 자식들보다 작다면, 더 큰 자식과 계속 교체하면서 아래로 내려가 힙 속성을 복원합니다.

예제

이제 위에서 만든 최종 힙에서 값 30(루트 노드)을 삭제한다고 가정해 보겠습니다. 루트를 제거한 후 마지막 요소를 루트로 옮기고, 자식 노드들과 비교하며 적절한 위치까지 내려보내면 힙의 구조와 최대 힙 속성이 다시 유지됩니다.

이러한 삭제 연산의 시간 복잡도는 트리의 높이에 비례하므로 O(log n)입니다. 힙의 삽입 연산 역시 O(log n)으로 처리되기 때문에, 최대 힙은 우선순위 큐(Priority Queue)를 구현하는 데 널리 활용됩니다.