정렬할 배열을 힙으로 만들기
일단 정렬을 하려면 힙을 만들어야 한다.
정렬할 1차원 데이터 10개가 있다.
complete binary tree 로 변경한다.
이런식으로 정렬한다.
1차원배열을 complete binary tree로 생각한다.
처음으로 leaf노드가 아닌 것 부터 시작한다. 16이 저장된 노드
levelnode들의 역순으로 노드들을 고려했을 때 leafnode가 아닌 첫번째 node이다.
자식이 하나인 7이 저장된 노드는 단독으로 본다면 heap으로 볼 수 있다. 16은 오른쪽 자식이 없으니, 서브트리에 대해서 heapify연산을 할 조건이 충족 된다.
16이 저장되어있는 노드로 heapify연산을 한다. ===> 변동사항없음.
14는 2보다 크다. ===> 위 아래가 바뀐다
둘다 heap이 충족된다.
3은 10보다 작으니 ===> 위 아래가 바뀐다.
3개가 heap 의 요소가 충족
16과 1이 바뀌고 1과 7이 바뀐다. ===> heap 충족
실제 프로그램 안에서는 배열안에서 정렬되어 있다.!
length[A] 정렬할 데이터의 개수
heap-size[A] 힙의 저장된 노드의 개수는 정렬할 노드의 개수와 같으니 length[A]와 같다.
맨마지만 노드의 인덱스가 n 의 부모노드 n/2
for i <- length[A]/2 downto I
do MAX-Heapify(A,i)
n은 node의 갯수
실질적으로 러프한 계산이다.
heapify node갯수가 n개라는것에 대한 계산이다.
maxheap은 부모는 자식보다 크다. 라는 것을 만족해야 한다.
전체에서 최댓값은 root에 있어야한다.
1. 힙을 만들고
2. 힙을 만드는 시간 복잡도가 힙정렬 시간 복잡도는
n log n이다.
HEAPSORT(a)
1. BUID-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)