선형 시간에 힙 만들기 Building Heap in Linear Time

힙을 만드는 방법

힙을 만들기 위해서 heapify라는 연산을 정의하겠다.

heapify(x): 노드 x의 왼쪽, 오른쪽 자식을 루트로 서브트리가 각각 힙일 때 노드 x를 루트로 하는 서브트리를 힙으로 만든다.

이 연산을 bottom-up으로 모든 노드에 대해서 수행해 주면 해당 트리는 힙이 된다.

Heapify의 시간 복잡도

heapify는 다음과 같은 알고리즘으로 수행할 수 있다.

1. 노드 x의 자식이 없다면 이미 힙이므로 종료한다.
2. 그게 아니라면(자식이 있다면) 자식 중 값이 더 큰 노드를 찾는다.
3. 해당 노드의 값이 노드 x의 값보다 작다면 이미 힙이므로 종료한다.
4. 그게 아니라면(1번에서 찾은 노드의 값이 노드 x의 값보다 크다면) 해당 노드와 노드 x를 swap한다.
5. 1번으로 돌아간다.

이 알고리즘은 상당히 간단하기에 우리는 heapify의 시간 복잡도가 노드 x를 루트로 하는 서브트리의 높이에 비례함을 쉽게 알 수 있다. 즉 전체 서브트리의 높이가 \( h \)이고 노드 x의 깊이가 \( d \)라면 heapify의 시간 복잡도는 \( O(h - d) \)이다.

Heapify를 모든 노드에 대해서 수행하면 시간 복잡도는?

heapify를 bottom-up으로 모든 노드에 대해서 수행해 주면 해당 트리는 힙이 된다고 했다. 이 전체 연산의 시간 복잡도를 구해 보자. 어떤 이진 트리에서 깊이 \( d \)에는 최대 \( 2^d \)개의 노드가 있다. 따라서 전체 트리의 높이가 \( h = \lceil \log_2{n} \rceil \)일 때 힙을 만드는 연산은 다음 식에 비례하는 시간 복잡도를 가진다:

$$ \sum_{d=0}^{h} 2^{d} (h-d) $$

이 식을 간단히 하는 것은 쭉 계산하기엔 상당히 복잡하므로 살짝의 변형을 주도록 하겠다. 급수를 계산할 때 간간이 접할 수 있는 테크닉이다. 편의를 위해 전체 식을 \( S \)로 두겠다:

$$ S = \sum_{d=0}^{h} 2^{d} (h-d) = 2^0(h-0)+2^1(h-1)+\cdots+2^h(h-h) $$

$$ 2S = 2^1(h-0)+2^2(h-1)+\cdots+2^{h+1}(h-h) $$

\( 2S - S = S \)를 계산해 주는데 \( 2^d \) 부분에서 \( d \)가 같은 항끼리 뺄셈해 주자:

$$ 2S-S=S=-2^0(h-0)+2^1((h-0)-(h-1))+\cdots +2^h((h-(h-1))-(h-h)) $$

$$ =-h+2^1+2^2+\cdots+2^h=-h+\frac{2(2^h-1)}{2-1}=2^{h+1}-2-h $$

이제 쭉 결과를 도출하면 된다:

$$ S = 2^{h+1}-2-h \leq 2^{h+1} = 2 \times 2^h = 2 \times 2 ^ {\lceil \log_2{n} \rceil} \leq 2 \times 2 ^ {\log_2{n} + 1} = 4n = O(n)$$