개발 공부 - [정렬] 힙 정렬(heap sort) -2 (Section 3)

(1과 이어서 강의)

만약에 루트만 힙 조건을 만족하지 않을 경우,

조건을 만족시키기 위해 자식들 중 더 큰 쪽이 루트보다 크면 교환한다.

그런 식으로 밑까지 내려 보냄.

요렇게 heap 조건을 만족시키는 이진 트리로 만듬.

 MAX-HEAPIFY : recursive version

MAX-HEAPIFY(A, i) // 노드 i를 루트로 하는 서브트리를 heapify 한다.

{

    if there is no child of A[i]

        return;

    k <- index of the biggest child of i;

    if A[i] ≥ A[k]

        return;

    exchange A[i] and A[k];

    MAX-HEAPIFY(A, k);

} //root 노드에 대한 heapify는 MAX-HEAPIFY(1)을 호출하면 됨

이거를 iterative version으로 변경도 가능하다.

MAX-HEAPIFY(A, i)

{

    while A[i] has a child do

    k <- index of the biggest child of i;

    if A[i] ≥ A[k]

        return;

    exchange A[i] and A[k];

    i = k;

end.

}

이거는 시간 복잡도를 생각해 보면 트리 높이(h) 보다 더 크게 걸릴 수는 없으므로

O(h) - complete binary 트리이므로 노드 수는 n

h = O(logn) 에서 약간 오차 있는 정도로 적용된다.