Heap Sort | Data Structure | Pusan National University

두 구간배열 앞쪽은 줄어드는 힙, 뒤쪽은 자라는 정렬 구간이다. 한 번 꺼낼 때마다 경계가 한 칸 앞으로 온다.

최대 힙과 오름차순루트의 최댓값을 뒤에 쌓으므로 최대 힙이면 오름차순, 최소 힙이면 내림차순이 된다.

안정성키가 같은 값들의 원래 순서가 정렬 뒤에도 유지되는 성질이다. 힙 정렬은 이를 보장하지 않는다.

루트를 힙 구간의 끝과 바꾸고 sift down하면 정렬 구간이 뒤에서 자란다

[9, 5, 6, 2, 3, 8, 1, 7, 4]를 제자리에서 정렬한다. 사용할 힙과 꺼낸 횟수를 바꾸면 힙 구간의 트리, 배열의 두 구간, 뒤로 보낸 값이 바뀐다.

사용할 힙

꺼낸 횟수 0

위 트리는 아직 힙 구간에 남은 값만 그린 것이고 초록 테두리 원이 다음에 꺼낼 루트다. 아래 배열에서 파란 칸이 힙 구간, 옅은 초록 칸이 정렬 구간이며 진한 초록 칸이 방금 뒤로 보낸 값, 검은 점선이 두 구간의 경계다.

같은 점수의 학생들이 입력 순서대로 남는지가 안정성이다

점수와 학생 이름표로 된 기록 여섯 개를 점수 오름차순으로 정렬한다. 정렬 방법을 바꾸면 같은 점수끼리의 순서가 입력과 같은지가 바뀐다.

정렬 방법

위 줄이 입력, 아래 줄이 정렬 결과다. 파란 칸은 80점, 초록 칸은 90점 기록이고 선은 같은 기록을 잇는다. 빨간 선은 같은 점수의 두 기록이 입력과 반대 순서로 나온 곳이다.

힙 정렬은 최악 시간 복잡도가 O(n log n)인 제자리 정렬이지만 안정적이지 않다

강의에서 다룬 세 정렬 방법의 최악 시간, 제자리 여부, 안정성을 나란히 놓는다.

정렬 방법	최악 시간	제자리	안정성
정렬된 앞부분에 하나씩 끼워 넣기	O(n²)	예	같은 키 뒤에 넣으면 안정적
BST에 넣고 중위 순회	O(n²)	아니요	중복 키 처리 규칙에 따름
힙 정렬	O(n log n)	예	불안정

행 하나가 정렬 방법 하나다. 초록 칸이 힙 정렬의 세 성질이다.

힙 정렬의 비용은 heapify 한 번 O(n)과 최댓값 꺼내기 n번 O(n log n)을 더한 것이다. 끼워 넣기와 BST 중위 순회는 최악 O(n²)이고 BST는 노드를 따로 만들어야 하지만, 힙 정렬은 최악에도 O(n log n)이면서 추가 배열이 필요 없다. 대신 같은 키의 순서는 보존하지 않으므로 그 순서를 지켜야 하는 문제에는 같은 키 뒤에 끼워 넣는 방법처럼 안정적인 정렬을 고른다.