Analysis of Algorithms | Time Complexity of building a heap

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다.
• 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

Heap을 구성하기 위한 시간 복잡도

BUILD-HEAP(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 
END

위의 의사코드는 배열 A를 입력받아 힙 자료구조로 만들어주는 기능을 한다. HEAPIFY 함수는 heap의 특성을 유지하게 해주는 함수이다. 코드를 보면 이진 힙(Binary Heap)으로 변환해주며 여기선 max heap으로 설명한다.

참고사항 : Max Heap과 Min Heap

Binary Heap에는 Min Heap과 Max Heap이 존재한다. Min Heap의 조건은 A[parent[i]] ≤ A[i]으로 parent 노드가 child 노드보다 작아야 하고 Max Heap의 조건은 A[parent[i]] ≥ A[i]으로 parent 노드가 child 노드보다 커야 한다.

참고사항 : HEAPIFY의 Loop 필요성

heap의 특성을 유지하게 해주는 HEAPIFY 함수가 1번만 수행될 경우 전체 트리의 heap 특성을 아래 그림과 같이 만족시켜주지 않을 수 있기에 Loop문이 필요하다. (∵ 한 번의 HEAPIFY는 부분 트리(3개 노드)에서의 대소 관계를 결정하기 때문에 전체 트리를 구성하는 모든 부분 트리를 순회하여 heap 특성을 유지했을 때 전체 heap이 완성된다.)

[2, 1, 3]에 대해서 1회의 HEAPIFY를 진행한 결과 반례가 발생하였다.

[2, 1, 3], [4, 1, 5] 두 개의 부분 트리에 대해 HEAPIFY를 진행하였으나 반례가 발생하였다.

간단하게 계산한 BUILD-HEAP 함수의 시간 복잡도

BUILD-HEAP 함수의 시간 복잡도를 간략하게 보면 for 문에서 $\cfrac{n}{2}$만큼 수행하므로 복잡도 관점에서 $O(n)$이다. 그러면 HEAPIFY 함수의 시간 복잡도에 따라 전체 시간 복잡도가 결정된다. max heap 성질로 유지하려는 함수를 정의하여 복잡도를 알아본다.

MAX-HEAPIFY(int i){
    int l = left(i), r= right(r);
    // i번째 노드의 왼/오른쪽 child 노드 선언
    int largest = i;
    // i번째 노드의 값이 가장 크다고 가정
    if (l < A.size() && A[l] > A[i]) largest = l;
    // l index가 배열의 범위를 넘어가는지, 최대값과 크기 비교
    if (r < A.size() && A[r] > A[largest]) largest = r;
    // r index가 배열의 범위를 넘어가는지, 최대값과 크기 비교
    if (largest != i){ // largest 값의 index가 i가 아니면
        swap(A[largest], A[i]);
        // largest index 값과 i index 값 치환
        MAX-HEAPIFY(largest);
        // HEAPiFY 함수를 재귀적으로 실행
    } 
}

위 코드를 트리 깊이만큼 진행하며 전체 트리 깊이는 ceil($\log_{2}{n}$)이다. 즉 $O(\log n)$이 되어 적당히 계산된 전체 BUILD-HEAP의 시간 복잡도는 $O(n \log n)$으로 보인다. 그러나 상계로 표현하기엔 적합할 진 몰라도 점근적 관점에서 tight하지 못하기 때문에 좀 더 파고들기로 했다.

좀 더 엄밀하게 계산한 BUILD-HEAP 함수의 시간 복잡도

BUILD-HEAP 함수는 주어진 배열에 대해 차례대로 heap에 넣어 삽입하지 않고 주어진 배열 자체적으로 BUILD-HEAP 함수를 수행하여 그대로 삽입했을 때 의도한 HEAP 구조의 완성을 목적으로 한다. BUILD-HEAP 함수에서 시작을 $\cfrac{heapsize}{2}$라 했으므로 child node가 존재하는 가장 마지막 부모 노드에서 출발한다. 그리고 1까지 반복하기에 tree를 역으로 타고 올라감을 알 수 있다. 다시 BUILD-HEAP 함수의 'do HEAPIFY(A, i)'를 보면 i의 값에 따라 수행 시간은 가변적이며HEAPIFY를 진행하는 노드가 속한 트리의 높이 h에 따라 결정된다. ($h = \lceil \log_2 k \rceil$, $O(h)$)

heap으로 만들 때 높이 $h$에서 어느 정도의 시간이 걸리는 지 알아야 시간 복잡도의 판단이 가능하다. 그러면 주어진 배열의 크기가 $n$일 때 높이가 $h$인 트리가 얼마나 나오는 지 확인해야 한다. (∵ 재귀적으로 작은 $h$에서 큰 $h$까지 반복하기 때문)

참고사항 : 크기가 $n$인 힙이 갖는 높이가 $h$인 부분 트리의 개수

결론부터 말하자면 높이 $h$인 부분 트리를 최대 $\lceil \cfrac{n}{2^{h+1}} \rceil$개 갖는다. 증명을 하면 먼저 완전 이진트리일 경우 $h=0$일 때 leaf node의 수와 동일하므로 $\lceil \cfrac{n}{2} \rceil$이 됨과 가정이 성립함을 알 수 있다. 귀납 추론을 위해 $h-1$에 대해 성립한다고 가정하자. $N_h$를 기존 트리 $T$의 높이 $h$에 위치한 노드 개수라고 정의하고 $T'$은 $T$의 leaf node들을 제외하여 생성된 트리라고 하자. $T'$의 노드 개수는 $n' = n - \lceil \cfrac{n}{2} \rceil = \lfloor \cfrac{n}{2} \rfloor$이 된다. 그러면 $T$의 leaf node를 제거한 트리가 $T'$이므로 $T$에서의 높이 $h$는 $T'$에서 $h-1$에 해당한다. 즉, $N_{h}$은 $T'$의 $h-1$ 높이에 있는 노드 개수를 의미하고 $N_h=N'_{h-1}$임을 알 수 있다. 앞에서 정의한 값을 대입하면 $\lceil \cfrac{n'}{2^h} \rceil = \lceil \lfloor \cfrac{n}{2}\rfloor/2^h \rceil \le \lceil \cfrac{n}{2}/2^h \rceil = \lceil \cfrac{n}{2^{h+1}} \rceil$이 된다.

BUILD-HEAP 함수의 전체 cost

1. $T(n) = \sum_{h=0}^{lg(n)}\lceil \cfrac{n}{2^{h+1}} \rceil \cdot O(h)$
2. 트리의 깊이는 주어진 $n$개의 노드와 로그 함수의 관계를 가지므로 $lg(n)$으로 표기하였다. 그리고 각 높이 $h$ 마다 최대한 가질 수 있는 부분 트리가 $\lceil \cfrac{n}{2^{h+1}} \rceil$이며 높이 $h$에서 HEAPIFY에 걸리는 시간이 매번 소요되므로 $O(h)$를 곱한다.
3. $= O(n\cdot \sum_{h=0}^{lg(n)}\cfrac{h}{2^h})$
4. 빅-오 표기법은 상계를 중점적으로 다루기 때문에 지수에 붙은 상수를 무시하여 결합하였다.
5. $= O(n\cdot\sum_{h=0}^{\infty}\cfrac{h}{2^h})$
6. 마찬 가지로 상계를 다루기에 $h$가 무한으로 발산한다고 가정하여 표기하였다.

이제 무한 급수의 합을 구해야 한다. $\sum_{n=0}^{\infty}x^n=\cfrac{1}{1-x}(x<1)$이고 양변을 미분하여 $x$를 곱하면 $\sum_{n=0}^{\infty}nx^n=\cfrac{x}{(1-x)^2}$가 된다. 구한 값을 대입하면 $O(n\cdot\cfrac{1}{(1-\cfrac{1}{2})^2}\cdot \cfrac{1}{2}) = O(2n) = O(n)$이 된다. 그러므로 BUILD-HEAP 함수의 시간 복잡도는 $O(n)$으로 대충 $O(n \log n)$이라고 추정한 결과보다 더 낮다.

참고자료

1. Time Complexity of building a heap
2. prove for the number of nodes with height h