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

 정렬할 배열을 힙으로 만들기

Build-max-heap(A)

1) heap-size[A] <- length[A] (정렬할 데이터의 개수)

2) for i <- └length[a]/2┘ downto 1

3) do MAX-heapify(A,1)

시간복잡도 O(n)

정렬을 하려면 먼저 데이터로 힙을 만들어야 함.

데이터는 정렬이 되어지지 않은 상태고 이걸로

complete binary tree를 맨들어서 heap으로 변경해야 함.

힙은 정렬에 있어서 매우 유리한 점이 있는데

MAX힙은 부모는 자식보다 크다는 것이므로

전체 트리 중 최대값은 반드시 root이다!

Heapsort

1. - 주어진 데이터로 힙을 만든다

2. - 힙에서 최대값(루트)를 가장 마지막 값과 바꾼다

3. - 힙의 크기가 1 줄어든 것으로 간주한다. 즉, 가장 마지막 값은 힙의 일부가 아닌 것으로 간주한다.

4. - 루트 노드에 대해서 HEAPIFY(1) 한다.

5. - 2~4번을 반복한다.

HEAPSORT(A)

1. BUILD-MAX-HEAP(A)             : O(n)

2. for i <- heap_size downto 2 do    : n-1 times

3. exchange A[1] <-> A[i]                : O(1)

4. heap_size <- heap_size -1            : O(1)

5. MAX-HEAPFIY(A,1)                :O(log2n)

TOTAL TIME : O(nlog2n)