Building Heap in Linear Time

처음 배열에서 힙을 구성할 때 선형시간으로 구성하는 방법이 있다. 일반적으로 각각의 원소를 삽입하는 방식으로 힙을 구성하면 자명하게 $O(N \lg N)$ 시간복잡도를 갖는다. 이를 $O(N)$에 해결할 수 있는 방법을 설명하겠다.

힙의 모양을 구성한 뒤에 맨 아래 정점부터 처리하는데, 부모 정점의 값보다 자신의 값이 우선순위가 더 높다면 부모 정점의 값과 자신의 값을 바꾼다. 이 뒤에 자신의 값의 우선순위가 자기 자식 정점의 값보다 낮을 수 있으므로 마찬가지로 재귀적으로 확인해준다. 이렇게 진행될 경우 아래에서 $h$ 높이에 있는 정점을 처리할 때, 최대 $h$번의 swap이 일어날 수 있다. 이를 수식으로 써서 나타내면 연산회수의 상한은 $n \times \sum{\frac{h}{2^{h-1}}}$ 이다.

$\sum{\frac{h}{2^{h-1}}} = 1 + \frac{2}{2} + \frac{3}{4} + \frac{4}{8} + \frac{5}{16} + \frac{6}{32} + \dots = (1 + \frac{1}{2} + \frac{1}{4} + \dots) + \frac{1}{2}\times(1+\frac{1}{2}+\frac{1}{4}+\dots)+\dots$

$1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots = 2$ 이므로 $\sum{\frac{h}{2^{h-1}}} = 4$ 가 된다. 따라서 위 방식으로 힙을 구성할 시 전체시간복잡도가 $O(N)$이 되는 것을 알 수 있다.

void make_heap() { // N: Heap size // A: Heap array for (int i=N;i>1;i--){ if (A[i>>1] < A[i]) continue; swap(A[i>>1], A[i]); int t = i; while (t+t <= N){ if (t+t+1 <= N && A[t+t+1] < A[t+t] && A[t+t+1] < A[t]){ swap(A[t], A[t+t+1]); t = t+t+1; } else if (A[t+t] < A[t]){ swap(A[t], A[t+t]); t <<= 1; } else break; } } }