티스토리 뷰

공부

Building Heap in Linear Time

전명우 2016.07.01 16:08

처음 배열에서 힙을 구성할 때 선형시간으로 구성하는 방법이 있다. 일반적으로 각각의 원소를 삽입하는 방식으로 힙을 구성하면 자명하게 $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)$이 되는 것을 알 수 있다.

저작자 표시
신고

'공부' 카테고리의 다른 글

Convex Hull Optimization  (4) 2016.08.23
가장 먼 두 점 구하기  (4) 2016.07.17
Building Heap in Linear Time  (2) 2016.07.01
String Matching Algorithm  (4) 2016.06.24
Persistent Segment Tree  (4) 2016.06.23
Divide & Conquer Optimization  (2) 2016.06.23
댓글
댓글쓰기 폼