힙(Heap) 자료구조에서의 삽입과 삭제 알고리즘 완벽 정리

이 글에서는 이진 힙(Binary Heap) 자료구조에 요소를 삽입하고 삭제하는 방법을 살펴봅니다. 힙은 완전 이진 트리의 한 형태로, 최대 힙(Max Heap)에서는 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같아야 합니다. 아래와 같은 초기 트리가 있다고 가정해 보겠습니다.

삽입 알고리즘

힙에 새로운 요소를 삽입할 때는 먼저 해당 요소를 힙의 마지막 위치에 추가합니다. 이후 부모 노드와 값을 비교하여 힙 속성(부모 ≥ 자식)이 만족될 때까지 위쪽으로 이동시키는데, 이 과정을 상향 재정렬(Up-Heapify)이라고 합니다. 삽입 연산의 시간 복잡도는 O(log n)입니다.

insert(heap, n, item):
Begin
    if heap is full, then exit
    else
        n := n + 1
        for i := n, i > 1, set i := i / 2 in each iteration, do
            if item <= heap[i/2], then break
            heap[i] = heap[i/2]
        done
    end if
    heap[i] := item
End

삽입 예시

위 힙에 값 30을 삽입하는 과정은 다음과 같습니다. 새 요소가 마지막 위치에 추가된 후, 부모 노드와 비교하며 조건이 충족될 때까지 위로 올라가는 것을 확인할 수 있습니다.

삭제 알고리즘

힙에서의 삭제는 일반적으로 루트 노드, 즉 최댓값을 제거하는 연산을 의미합니다. 삭제 시에는 마지막 요소를 루트 위치로 옮긴 뒤, 두 자식 노드 중 더 큰 값과 비교하면서 힙 속성이 복원될 때까지 아래쪽으로 이동시킵니다. 이 과정을 하향 재정렬(Down-Heapify)이라고 하며, 삭제 연산 역시 O(log n)의 시간 복잡도를 가집니다.

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

삭제 예시

이제 앞서 완성한 최종 힙에서 30을 삭제하는 과정을 살펴보겠습니다. 루트가 제거된 후 마지막 요소가 루트로 이동하고, 자식 노드들과의 비교를 통해 힙 구조가 다시 정렬되는 모습을 확인할 수 있습니다.