DataStructure] 힙(Heap, 히프) 만들기 - 2

앞선 글에서(링크) 이야기했던 대로, BuildHeap Algorithm은 다음과 같은 순서로 알고리즘이 진행된다.

가장 먼저 i=[n/2]=15로 시작하여 DownHeap을 호출해, i가 1이 될 때까지 총 15회 DownHeap을 호출한다.

이 때 i에 대응되는 노드를 '시작 노드'라고 했을 때, DownHeap은 시작 노드의 값을 자식 노드들의 값과 비교해 힙 조건이 만족되는 순간까지 시작 노드의 값을 아래 쪽으로 자리를 바꾸며 이동시키는 작업을 실시한다.

즉, 시작 노드를 루트 노드로 간주하여 부분 힙를 구성하고,

그 부분 힙을 합쳐나가는 과정을 거치는 것이다.

힙을 만드는 알고리즘 BuildHeap의 시간 복잡도가 O(n)인 이유는 아래와 같이 증명할 수 있다.

n=31(노드 수 31개)인 경우, 최악의 경우

최악의 경우, 시작 노드가 1층 내려가는 것으로 끝이 나기 때문에,

31개의 노드를 가지고 있는 힙의 경우, 시작 노드가 4번째 층(위 그림에서 가장 밑의 화살표)까지 내려가 이파리 노드에 저장된다. 이 때, 한 개 층 내려가는 일은 DownHeap의 호출(상수 시간)에 따라 이루어진다.

결국 BuildHeap의 시간 복잡도는 "각 층의 노드 수 X 층 수"로, 이를 아래와 같이 수식으로 표현할 수 있다.