힙 정렬.md

힙 정렬

문제

정렬되지 않은 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)
힙 절차는 재귀적으로 호출하여 하향식 방식으로 힙을 빌드한다.

구현

• 자바
• C++
• 파이썬
• 루비
• C-Sharp
• C
• 자바스크립트

영상 URL

힙 정렬 알고리즘에 대한 영상 설명