Twinparadox Factory

앞선 글에서(링크) 이야기했던 대로, BuildHeap Algorithm은 다음과 같은 순서로 알고리즘이 진행된다. 가장 먼저 i=[n/2]=15로 시작하여 DownHeap을 호출해, i가 1이 될 때까지 총 15회 DownHeap을 호출한다.이 때 i에 대응되는 노드를 '시작 노드'라고 했을 때, DownHeap은 시작 노드의 값을 자식 노드들의 값과 비교해 힙 조건이 만족되는 순간까지 시작 노드의 값을 아래 쪽으로 자리를 바꾸며 이동시키는 작업을 실시한다. 즉, 시작 노드를 루트 노드로 간주하여 부분 힙를 구성하고,그 부분 힙을 합쳐나가는 과정을 거치는 것이다. 힙을 만드는 알고리즘 BuildHeap의 시간 복잡도가 O(n)인 이유는 아래와 같이 증명할 수 있다. n=31(노드 수 31개)인 경우, ..

힙(혹은 히프)은 최솟값(또는 최댓값)을 빠른 시간에 접근하게 만들어진 자료구조로, 최댓값을 접근하려면 최대힙을, 최솟값을 접근하려면 최소힙을 사용한다. 두 힙은 대칭적인 관계를 갖고 있기 때문에, 하나를 이해하면 다른 힙은 쉽게 이해할 수 있다. 힙에 대해 정확히 모르는 사람들을 위해서 이해를 돕기 위한 그림과 힙의 조건에 대해서 이야기를 잠깐 하겠다. 힙은 위 그림처럼, 각 노드의 값이 자식 노드들의 값보다 크거나 작은(클 경우 최대힙, 작을 경우 최소힙) 완전이진트리를 뜻한다. 거의 대부분이 정렬 파트를 다루면서 힙 정렬을 통해 이 구조에 대해서 아는 경우가 대부분이다. 오늘은 힙이 어떤 식으로 생겼는지 보는 것보다는, 힙 자료구조를 구성하는데 요구되는 시간복잡도가 O(n)인 것에 대해서 이야기를 ..