Heapsort

1. Max-heapify (A,i) : i의 위치에서 left, right child와 비교하여 가장 큰 값이 아닌 경우에 큰값과 swap하고 해당 값에 대해서 재귀적으로 Max-heapify 적용 => 시간복잡도 O(logn)
2. Max-heap 만들기 : A가 parent 노드인 A.length/2부터 하나씩 위로 올라가면서 max-heap을 만들어주면 된다.

def Build-max-heap(A):
  A.heap-size = A.length
  for i = A.length /2 downto 1
      Max-heapify(A,i)

3. Heapsort : heap 구조를 이용해서 sort 결과를 취득하는 방식. 먼저 max-heap을 구성하고 root node를 기록하고 가장 마지막 leaf 노드와 교체한다. 그 다음 max-heapify(A,1)을 호출하여 다시 max-heap으로 만들어준다.

def HeapSort(A):
  Build-max-heap(A)  # max-heap을 우선 구성한다. O(nlogn)
  for i = A.length downto 2 # Max-heapfy를 n번 반복한다. O(nlogn)
    swap (A[1],A[i])
    A.heap-size  = A.heap-size -1
    Max-heapify(A,1)

최종 시간 복잡도 : O(nlogn)