[Introduction to Algorithms] 힙 정렬 알고리즘

1) 개요

- 힙 정렬 알고리즘은 BUILD-MAX-HEAP으로 입력 배열 A[1...n](n = A.length]를 최대 힙으로 만들면서 시작한다.

  최대 원소가 루트 A[1]에 저장되어 있으므로 이것을 A[n]과 교환하면 정확히 마지막 자리에 넣을 수 있다.

  이제 힙에서 (A.heap-size를 줄여서) 노드 n을 "제거"하면 A[1..(n-1)]을 최대 힙으로 만드는 것은 그리 어렵지 않다.

  

- 루트의 자식들은 최대 힙으로 남아 있지만, 새로운 루트는 최대 힙 특성을 어길 수 있다.

  따라서 최대 힙 특성을 다시 지키도록 MAX-HEAPIFY(A,1)을 호출한다.

  힙 정렬 알고리즘은 이 과정을 힙 크기가 n-1일때부터 2로 줄어들때까지 반복한다. 

 

HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i A.length downto 2
    exchange A[1] with A[i]
    A.heap-size = A.heap-size -1 
    MAX-HEAPIFY(A, 1)

 

- 그림 6.4는 최대 힙이 초기에 만들어진 다음 힙 정렬의 동작의 예를 보여준다.

   2-5행에 있는 for 루프의 반복은 항상 최대 힙으로 시작한다. 

   

- BUILD-MAX-HEAP이 O(n) 시간 걸리고 MAX-HEAPFIY를 n-1번 실행하는 것이 각각 O(lgn) 시간이 걸리므로

  HEAPSORT의 수행시간은 O(nlgn)이다.