개요
이번 글에서는 이진 최대 힙(Binary Max Heap) 자료구조에 새로운 요소를 삽입하는 방법을 살펴보겠습니다. 최대 힙은 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같은 성질(힙 속성)을 만족하는 완전 이진 트리입니다. 따라서 새 요소를 단순히 추가하는 것만으로는 부족하고, 삽입 후 힙 속성을 다시 복원하는 과정이 필요합니다.
삽입 과정을 설명하기 위해 아래와 같은 초기 트리가 있다고 가정해 보겠습니다.
삽입 알고리즘
최대 힙에 요소를 삽입하는 절차는 다음과 같습니다.
- 새 요소를 힙의 마지막 위치(배열의 끝)에 임시로 배치합니다.
- 새 요소를 부모 노드와 비교합니다. 부모보다 크면 두 값을 교환하고 한 단계 위로 올라갑니다(상향식 재정렬, Sift-up).
- 부모가 더 크거나 같아지면, 즉 힙 속성이 만족되면 과정을 종료합니다.
이를 의사 코드(pseudocode)로 표현하면 다음과 같습니다.
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
알고리즘 동작 설명
- heap: 힙을 저장하는 배열
- n: 현재 힙에 저장된 요소의 개수
- item: 삽입할 새로운 값
먼저 힙이 가득 찼는지 확인하고, 여유가 있으면 요소 개수 n을 하나 늘립니다. 이후 인덱스 i를 마지막 위치에서 시작해 매 반복마다 i/2(부모 노드)로 이동하면서, 삽입할 값 item이 부모보다 작거나 같으면 반복을 멈춥니다. 그렇지 않으면 부모 값을 아래로 내리고 계속 위로 올라갑니다. 최종적으로 빈자리가 된 위치 i에 item을 저장하면 삽입이 완료됩니다.
삽입 예제
이제 위의 힙에 값 30을 삽입한다고 가정해 보겠습니다.
30은 먼저 힙의 마지막 위치에 놓인 뒤, 부모 노드와 비교하여 부모보다 클 경우 위로 교환됩니다. 이 과정을 힙 속성이 만족될 때까지 반복하면, 30은 자신의 올바른 위치에 안착하게 됩니다.
시간 복잡도
삽입 연산은 트리의 높이만큼만 비교와 교환이 일어나므로, 완전 이진 트리의 높이는 log n이기 때문에 시간 복잡도는 O(log n)입니다. 공간 복잡도는 추가 배열 없이 제자리에서 수행되므로 O(1)입니다.