인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

Heapsort

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

  수도코드

  

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

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

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

• 2~4번을 반복한다.

가장 큰 수부터 배열의 뒷자리를 차지하며 정렬이 된다.

수도코드