티스토리 뷰

공부

Building Heap in Linear Time

전명우 2016. 7. 1. 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
가장 먼 두 점 구하기  (6) 2016.07.17
String Matching Algorithms  (5) 2016.06.24
Persistent Segment Tree  (6) 2016.06.23
Divide & Conquer Optimization  (3) 2016.06.23
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함