정렬되지 않은 n개의 원소로 이루어진 배열이 주어졌을 때, 배열을 정렬하는 함수를 작성하라
- 입력 데이터에서 최대 힙을 빌드한다.
- 이때, 가장 큰 원소가 힙의 루트에 저장된다. 해당 원소를 힙의 마지막 원소로 교체한 뒤, 힙의 사이즈를 1 줄인다.
- 힙의 사이즈가 1보다 크다면 위 과정을 반복한다.
O(n log n) 최악의 경우
O(n log n) (고유 키)
or O(n) (동일 키) 최선의 경우
O(n log n) 평균 복잡도
O(1) 최악의 경우
입력 원소 : 4, 10, 3, 5, 1
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
괄호 안의 숫자는 데이터의 배열 인덱스를 나타낸다.
1번 인덱스에 힙 절차 적용 :
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
0번 인덱스의 힙 절차 적용:
10(0)
/ \
5(1) 3(2)
/ \
4(3) 1(4)
힙 절차는 재귀적으로 호출하여 하향식 방식으로 힙을 빌드한다.
