11.7 힙 정렬¶
참고
이 절을 읽기 전에 '힙' 장을 먼저 학습하자.
힙 정렬(heap sort)은 힙 자료 구조를 이용한 효율적인 정렬 알고리즘이다. 이미 배운 '힙 구성 연산'과 '힙에서 원소를 꺼내는 연산'으로 구현할 수 있다.
- 배열을 입력받아 최소 힙을 구성한다. 이때 가장 작은 원소가 힙의 루트에 놓인다.
- 힙에서 원소를 계속 꺼내며 순서대로 기록하면 오름차순으로 정렬된 수열을 얻는다.
위 방법도 가능하지만 꺼낸 원소를 저장할 추가 배열이 필요하여 공간을 낭비한다. 실제로는 보통 더 간결한 구현 방식을 사용한다.
11.7.1 알고리즘 과정¶
배열의 길이가 \(n\)일 때 힙 정렬의 과정은 아래 그림(11-12)과 같다.
- 배열을 입력받아 최대 힙을 구성한다. 완료하면 가장 큰 원소가 힙의 루트에 놓인다.
- 힙의 루트 원소(첫 번째 원소)와 끝 원소(마지막 원소)를 교환한다. 교환 후 힙의 길이는 \(1\) 줄고, 정렬된 원소 수는 \(1\) 늘어난다.
- 힙의 루트 원소부터 위에서 아래로 힙 재정렬(sift down)을 수행한다. 재정렬을 마치면 힙의 성질이 복구된다.
2.단계와3.단계를 반복한다. \(n - 1\) 회 반복하면 배열 정렬이 완료된다.
참고
힙에서 원소를 꺼내는 연산에도 2. 단계와 3. 단계가 포함되며, 실제로 원소를 꺼내는 단계가 하나 더 있을 뿐이다.
그림 11-12 힙 정렬 단계
구현에서는 '힙' 장과 동일한 하향 힙 재정렬 함수 sift_down()을 사용한다. 가장 큰 원소를 꺼낼 때마다 힙의 길이가 줄어들므로, 현재 유효한 힙 길이를 지정하는 매개변수 \(n\)을 sift_down()에 추가해야 한다. 코드는 다음과 같다.
heap_sort.py
def sift_down(nums: list[int], n: int, i: int):
"""길이가 n인 힙에서 노드 i부터 위에서 아래로 힙 재정렬"""
while True:
# 노드 i, l, r 중 값이 가장 큰 노드를 찾아 ma로 표시한다
l = 2 * i + 1
r = 2 * i + 2
ma = i
if l < n and nums[l] > nums[ma]:
ma = l
if r < n and nums[r] > nums[ma]:
ma = r
# 노드 i의 값이 가장 크거나 인덱스 l, r이 범위를 벗어나면 힙을 더 재정렬할 필요가 없으므로 종료한다
if ma == i:
break
# 두 노드를 교환한다
nums[i], nums[ma] = nums[ma], nums[i]
# 아래쪽으로 힙 재정렬을 반복한다
i = ma
def heap_sort(nums: list[int]):
"""힙 정렬"""
# 힙 구성 연산: 리프 노드를 제외한 모든 노드에 힙 재정렬을 수행한다
for i in range(len(nums) // 2 - 1, -1, -1):
sift_down(nums, len(nums), i)
# 힙에서 최댓값을 꺼내는 작업을 n-1회 반복한다
for i in range(len(nums) - 1, 0, -1):
# 루트 노드와 가장 오른쪽 리프 노드를 교환한다(첫 원소와 마지막 원소 교환)
nums[0], nums[i] = nums[i], nums[0]
# 루트 노드에서 시작하여 위에서 아래로 힙을 재정렬한다
sift_down(nums, i, 0)
heap_sort.cpp
/* 길이가 n인 힙에서 노드 i부터 위에서 아래로 힙 재정렬 */
void siftDown(vector<int> &nums, int n, int i) {
while (true) {
// 노드 i, l, r 중 값이 가장 큰 노드를 찾아 ma로 표시한다
int l = 2 * i + 1;
int r = 2 * i + 2;
int ma = i;
if (l < n && nums[l] > nums[ma])
ma = l;
if (r < n && nums[r] > nums[ma])
ma = r;
// 노드 i의 값이 가장 크거나 인덱스 l, r이 범위를 벗어나면 힙을 더 재정렬할 필요가 없으므로 종료한다
if (ma == i) {
break;
}
// 두 노드를 교환한다
swap(nums[i], nums[ma]);
// 아래쪽으로 힙 재정렬을 반복한다
i = ma;
}
}
/* 힙 정렬 */
void heapSort(vector<int> &nums) {
// 힙 구성 연산: 리프 노드를 제외한 모든 노드에 힙 재정렬을 수행한다
for (int i = nums.size() / 2 - 1; i >= 0; --i) {
siftDown(nums, nums.size(), i);
}
// 힙에서 최댓값을 꺼내는 작업을 n-1회 반복한다
for (int i = nums.size() - 1; i > 0; --i) {
// 루트 노드와 가장 오른쪽 리프 노드를 교환한다(첫 원소와 마지막 원소 교환)
swap(nums[0], nums[i]);
// 루트 노드에서 시작하여 위에서 아래로 힙을 재정렬한다
siftDown(nums, i, 0);
}
}
heap_sort.java
/* 길이가 n인 힙에서 노드 i부터 위에서 아래로 힙 재정렬 */
void siftDown(int[] nums, int n, int i) {
while (true) {
// 노드 i, l, r 중 값이 가장 큰 노드를 찾아 ma로 표시한다
int l = 2 * i + 1;
int r = 2 * i + 2;
int ma = i;
if (l < n && nums[l] > nums[ma])
ma = l;
if (r < n && nums[r] > nums[ma])
ma = r;
// 노드 i의 값이 가장 크거나 인덱스 l, r이 범위를 벗어나면 힙을 더 재정렬할 필요가 없으므로 종료한다
if (ma == i)
break;
// 두 노드를 교환한다
int temp = nums[i];
nums[i] = nums[ma];
nums[ma] = temp;
// 아래쪽으로 힙 재정렬을 반복한다
i = ma;
}
}
/* 힙 정렬 */
void heapSort(int[] nums) {
// 힙 구성 연산: 리프 노드를 제외한 모든 노드에 힙 재정렬을 수행한다
for (int i = nums.length / 2 - 1; i >= 0; i--) {
siftDown(nums, nums.length, i);
}
// 힙에서 최댓값을 꺼내는 작업을 n-1회 반복한다
for (int i = nums.length - 1; i > 0; i--) {
// 루트 노드와 가장 오른쪽 리프 노드를 교환한다(첫 원소와 마지막 원소 교환)
int tmp = nums[0];
nums[0] = nums[i];
nums[i] = tmp;
// 루트 노드에서 시작하여 위에서 아래로 힙을 재정렬한다
siftDown(nums, i, 0);
}
}
heap_sort.cs
/* 길이가 n인 힙에서 노드 i부터 위에서 아래로 힙 재정렬 */
void SiftDown(int[] nums, int n, int i) {
while (true) {
// 노드 i, l, r 중 값이 가장 큰 노드를 찾아 ma로 표시한다
int l = 2 * i + 1;
int r = 2 * i + 2;
int ma = i;
if (l < n && nums[l] > nums[ma])
ma = l;
if (r < n && nums[r] > nums[ma])
ma = r;
// 노드 i의 값이 가장 크거나 인덱스 l, r이 범위를 벗어나면 힙을 더 재정렬할 필요가 없으므로 종료한다
if (ma == i)
break;
// 두 노드를 교환한다
(nums[ma], nums[i]) = (nums[i], nums[ma]);
// 아래쪽으로 힙 재정렬을 반복한다
i = ma;
}
}
/* 힙 정렬 */
void HeapSort(int[] nums) {
// 힙 구성 연산: 리프 노드를 제외한 모든 노드에 힙 재정렬을 수행한다
for (int i = nums.Length / 2 - 1; i >= 0; i--) {
SiftDown(nums, nums.Length, i);
}
// 힙에서 최댓값을 꺼내는 작업을 n-1회 반복한다
for (int i = nums.Length - 1; i > 0; i--) {
// 루트 노드와 가장 오른쪽 리프 노드를 교환한다(첫 원소와 마지막 원소 교환)
(nums[i], nums[0]) = (nums[0], nums[i]);
// 루트 노드에서 시작하여 위에서 아래로 힙을 재정렬한다
SiftDown(nums, i, 0);
}
}
heap_sort.go
/* 길이가 n인 힙에서 노드 i부터 위에서 아래로 힙 재정렬 */
func siftDown(nums *[]int, n, i int) {
for true {
// 노드 i, l, r 중 값이 가장 큰 노드를 찾아 ma로 표시한다
l := 2*i + 1
r := 2*i + 2
ma := i
if l < n && (*nums)[l] > (*nums)[ma] {
ma = l
}
if r < n && (*nums)[r] > (*nums)[ma] {
ma = r
}
// 노드 i의 값이 가장 크거나 인덱스 l, r이 범위를 벗어나면 힙을 더 재정렬할 필요가 없으므로 종료한다
if ma == i {
break
}
// 두 노드를 교환한다
(*nums)[i], (*nums)[ma] = (*nums)[ma], (*nums)[i]
// 아래쪽으로 힙 재정렬을 반복한다
i = ma
}
}
/* 힙 정렬 */
func heapSort(nums *[]int) {
// 힙 구성 연산: 리프 노드를 제외한 모든 노드에 힙 재정렬을 수행한다
for i := len(*nums)/2 - 1; i >= 0; i-- {
siftDown(nums, len(*nums), i)
}
// 힙에서 최댓값을 꺼내는 작업을 n-1회 반복한다
for i := len(*nums) - 1; i > 0; i-- {
// 루트 노드와 가장 오른쪽 리프 노드를 교환한다(첫 원소와 마지막 원소 교환)
(*nums)[0], (*nums)[i] = (*nums)[i], (*nums)[0]
// 루트 노드에서 시작하여 위에서 아래로 힙을 재정렬한다
siftDown(nums, i, 0)
}
}
heap_sort.swift
/* 길이가 n인 힙에서 노드 i부터 위에서 아래로 힙 재정렬 */
func siftDown(nums: inout [Int], n: Int, i: Int) {
var i = i
while true {
// 노드 i, l, r 중 값이 가장 큰 노드를 찾아 ma로 표시한다
let l = 2 * i + 1
let r = 2 * i + 2
var ma = i
if l < n, nums[l] > nums[ma] {
ma = l
}
if r < n, nums[r] > nums[ma] {
ma = r
}
// 노드 i의 값이 가장 크거나 인덱스 l, r이 범위를 벗어나면 힙을 더 재정렬할 필요가 없으므로 종료한다
if ma == i {
break
}
// 두 노드를 교환한다
nums.swapAt(i, ma)
// 아래쪽으로 힙 재정렬을 반복한다
i = ma
}
}
/* 힙 정렬 */
func heapSort(nums: inout [Int]) {
// 힙 구성 연산: 리프 노드를 제외한 모든 노드에 힙 재정렬을 수행한다
for i in stride(from: nums.count / 2 - 1, through: 0, by: -1) {
siftDown(nums: &nums, n: nums.count, i: i)
}
// 힙에서 최댓값을 꺼내는 작업을 n-1회 반복한다
for i in nums.indices.dropFirst().reversed() {
// 루트 노드와 가장 오른쪽 리프 노드를 교환한다(첫 원소와 마지막 원소 교환)
nums.swapAt(0, i)
// 루트 노드에서 시작하여 위에서 아래로 힙을 재정렬한다
siftDown(nums: &nums, n: i, i: 0)
}
}
heap_sort.js
/* 길이가 n인 힙에서 노드 i부터 위에서 아래로 힙 재정렬 */
function siftDown(nums, n, i) {
while (true) {
// 노드 i, l, r 중 값이 가장 큰 노드를 찾아 ma로 표시한다
let l = 2 * i + 1;
let r = 2 * i + 2;
let ma = i;
if (l < n && nums[l] > nums[ma]) {
ma = l;
}
if (r < n && nums[r] > nums[ma]) {
ma = r;
}
// 노드 i의 값이 가장 크거나 인덱스 l, r이 범위를 벗어나면 힙을 더 재정렬할 필요가 없으므로 종료한다
if (ma === i) {
break;
}
// 두 노드를 교환한다
[nums[i], nums[ma]] = [nums[ma], nums[i]];
// 아래쪽으로 힙 재정렬을 반복한다
i = ma;
}
}
/* 힙 정렬 */
function heapSort(nums) {
// 힙 구성 연산: 리프 노드를 제외한 모든 노드에 힙 재정렬을 수행한다
for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
siftDown(nums, nums.length, i);
}
// 힙에서 최댓값을 꺼내는 작업을 n-1회 반복한다
for (let i = nums.length - 1; i > 0; i--) {
// 루트 노드와 가장 오른쪽 리프 노드를 교환한다(첫 원소와 마지막 원소 교환)
[nums[0], nums[i]] = [nums[i], nums[0]];
// 루트 노드에서 시작하여 위에서 아래로 힙을 재정렬한다
siftDown(nums, i, 0);
}
}
heap_sort.ts
/* 길이가 n인 힙에서 노드 i부터 위에서 아래로 힙 재정렬 */
function siftDown(nums: number[], n: number, i: number): void {
while (true) {
// 노드 i, l, r 중 값이 가장 큰 노드를 찾아 ma로 표시한다
let l = 2 * i + 1;
let r = 2 * i + 2;
let ma = i;
if (l < n && nums[l] > nums[ma]) {
ma = l;
}
if (r < n && nums[r] > nums[ma]) {
ma = r;
}
// 노드 i의 값이 가장 크거나 인덱스 l, r이 범위를 벗어나면 힙을 더 재정렬할 필요가 없으므로 종료한다
if (ma === i) {
break;
}
// 두 노드를 교환한다
[nums[i], nums[ma]] = [nums[ma], nums[i]];
// 아래쪽으로 힙 재정렬을 반복한다
i = ma;
}
}
/* 힙 정렬 */
function heapSort(nums: number[]): void {
// 힙 구성 연산: 리프 노드를 제외한 모든 노드에 힙 재정렬을 수행한다
for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
siftDown(nums, nums.length, i);
}
// 힙에서 최댓값을 꺼내는 작업을 n-1회 반복한다
for (let i = nums.length - 1; i > 0; i--) {
// 루트 노드와 가장 오른쪽 리프 노드를 교환한다(첫 원소와 마지막 원소 교환)
[nums[0], nums[i]] = [nums[i], nums[0]];
// 루트 노드에서 시작하여 위에서 아래로 힙을 재정렬한다
siftDown(nums, i, 0);
}
}
heap_sort.dart
/* 길이가 n인 힙에서 노드 i부터 위에서 아래로 힙 재정렬 */
void siftDown(List<int> nums, int n, int i) {
while (true) {
// 노드 i, l, r 중 값이 가장 큰 노드를 찾아 ma로 표시한다
int l = 2 * i + 1;
int r = 2 * i + 2;
int ma = i;
if (l < n && nums[l] > nums[ma]) ma = l;
if (r < n && nums[r] > nums[ma]) ma = r;
// 노드 i의 값이 가장 크거나 인덱스 l, r이 범위를 벗어나면 힙을 더 재정렬할 필요가 없으므로 종료한다
if (ma == i) break;
// 두 노드를 교환한다
int temp = nums[i];
nums[i] = nums[ma];
nums[ma] = temp;
// 아래쪽으로 힙 재정렬을 반복한다
i = ma;
}
}
/* 힙 정렬 */
void heapSort(List<int> nums) {
// 힙 구성 연산: 리프 노드를 제외한 모든 노드에 힙 재정렬을 수행한다
for (int i = nums.length ~/ 2 - 1; i >= 0; i--) {
siftDown(nums, nums.length, i);
}
// 힙에서 최댓값을 꺼내는 작업을 n-1회 반복한다
for (int i = nums.length - 1; i > 0; i--) {
// 루트 노드와 가장 오른쪽 리프 노드를 교환한다(첫 원소와 마지막 원소 교환)
int tmp = nums[0];
nums[0] = nums[i];
nums[i] = tmp;
// 루트 노드에서 시작하여 위에서 아래로 힙을 재정렬한다
siftDown(nums, i, 0);
}
}
heap_sort.rs
/* 길이가 n인 힙에서 노드 i부터 위에서 아래로 힙 재정렬 */
fn sift_down(nums: &mut [i32], n: usize, mut i: usize) {
loop {
// 노드 i, l, r 중 값이 가장 큰 노드를 찾아 ma로 표시한다
let l = 2 * i + 1;
let r = 2 * i + 2;
let mut ma = i;
if l < n && nums[l] > nums[ma] {
ma = l;
}
if r < n && nums[r] > nums[ma] {
ma = r;
}
// 노드 i의 값이 가장 크거나 인덱스 l, r이 범위를 벗어나면 힙을 더 재정렬할 필요가 없으므로 종료한다
if ma == i {
break;
}
// 두 노드를 교환한다
nums.swap(i, ma);
// 아래쪽으로 힙 재정렬을 반복한다
i = ma;
}
}
/* 힙 정렬 */
fn heap_sort(nums: &mut [i32]) {
// 힙 구성 연산: 리프 노드를 제외한 모든 노드에 힙 재정렬을 수행한다
for i in (0..nums.len() / 2).rev() {
sift_down(nums, nums.len(), i);
}
// 힙에서 최댓값을 꺼내는 작업을 n-1회 반복한다
for i in (1..nums.len()).rev() {
// 루트 노드와 가장 오른쪽 리프 노드를 교환한다(첫 원소와 마지막 원소 교환)
nums.swap(0, i);
// 루트 노드에서 시작하여 위에서 아래로 힙을 재정렬한다
sift_down(nums, i, 0);
}
}
heap_sort.c
/* 길이가 n인 힙에서 노드 i부터 위에서 아래로 힙 재정렬 */
void siftDown(int nums[], int n, int i) {
while (1) {
// 노드 i, l, r 중 값이 가장 큰 노드를 찾아 ma로 표시한다
int l = 2 * i + 1;
int r = 2 * i + 2;
int ma = i;
if (l < n && nums[l] > nums[ma])
ma = l;
if (r < n && nums[r] > nums[ma])
ma = r;
// 노드 i의 값이 가장 크거나 인덱스 l, r이 범위를 벗어나면 힙을 더 재정렬할 필요가 없으므로 종료한다
if (ma == i) {
break;
}
// 두 노드를 교환한다
int temp = nums[i];
nums[i] = nums[ma];
nums[ma] = temp;
// 아래쪽으로 힙 재정렬을 반복한다
i = ma;
}
}
/* 힙 정렬 */
void heapSort(int nums[], int n) {
// 힙 구성 연산: 리프 노드를 제외한 모든 노드에 힙 재정렬을 수행한다
for (int i = n / 2 - 1; i >= 0; --i) {
siftDown(nums, n, i);
}
// 힙에서 최댓값을 꺼내는 작업을 n-1회 반복한다
for (int i = n - 1; i > 0; --i) {
// 루트 노드와 가장 오른쪽 리프 노드를 교환한다(첫 원소와 마지막 원소 교환)
int tmp = nums[0];
nums[0] = nums[i];
nums[i] = tmp;
// 루트 노드에서 시작하여 위에서 아래로 힙을 재정렬한다
siftDown(nums, i, 0);
}
}
heap_sort.kt
/* 길이가 n인 힙에서 노드 i부터 위에서 아래로 힙 재정렬 */
fun siftDown(nums: IntArray, n: Int, li: Int) {
var i = li
while (true) {
// 노드 i, l, r 중 값이 가장 큰 노드를 찾아 ma로 표시한다
val l = 2 * i + 1
val r = 2 * i + 2
var ma = i
if (l < n && nums[l] > nums[ma])
ma = l
if (r < n && nums[r] > nums[ma])
ma = r
// 노드 i의 값이 가장 크거나 인덱스 l, r이 범위를 벗어나면 힙을 더 재정렬할 필요가 없으므로 종료한다
if (ma == i)
break
// 두 노드를 교환한다
val temp = nums[i]
nums[i] = nums[ma]
nums[ma] = temp
// 아래쪽으로 힙 재정렬을 반복한다
i = ma
}
}
/* 힙 정렬 */
fun heapSort(nums: IntArray) {
// 힙 구성 연산: 리프 노드를 제외한 모든 노드에 힙 재정렬을 수행한다
for (i in nums.size / 2 - 1 downTo 0) {
siftDown(nums, nums.size, i)
}
// 힙에서 최댓값을 꺼내는 작업을 n-1회 반복한다
for (i in nums.size - 1 downTo 1) {
// 루트 노드와 가장 오른쪽 리프 노드를 교환한다(첫 원소와 마지막 원소 교환)
val temp = nums[0]
nums[0] = nums[i]
nums[i] = temp
// 루트 노드에서 시작하여 위에서 아래로 힙을 재정렬한다
siftDown(nums, i, 0)
}
}
heap_sort.rb
### 길이가 n인 힙에서 노드 i부터 위에서 아래로 힙 재정렬 ###
def sift_down(nums, n, i)
while true
# 노드 i, l, r 중 값이 가장 큰 노드를 찾아 ma로 표시한다
l = 2 * i + 1
r = 2 * i + 2
ma = i
ma = l if l < n && nums[l] > nums[ma]
ma = r if r < n && nums[r] > nums[ma]
# 노드 i의 값이 가장 크거나 인덱스 l, r이 범위를 벗어나면 힙을 더 재정렬할 필요가 없으므로 종료한다
break if ma == i
# 두 노드를 교환한다
nums[i], nums[ma] = nums[ma], nums[i]
# 아래쪽으로 힙 재정렬을 반복한다
i = ma
end
end
### 힙 정렬 ###
def heap_sort(nums)
# 힙 구성 연산: 리프 노드를 제외한 모든 노드에 힙 재정렬을 수행한다
(nums.length / 2 - 1).downto(0) do |i|
sift_down(nums, nums.length, i)
end
# 힙에서 최댓값을 꺼내는 작업을 n-1회 반복한다
(nums.length - 1).downto(1) do |i|
# 루트 노드와 가장 오른쪽 리프 노드를 교환한다(첫 원소와 마지막 원소 교환)
nums[0], nums[i] = nums[i], nums[0]
# 루트 노드에서 시작하여 위에서 아래로 힙을 재정렬한다
sift_down(nums, i, 0)
end
end
코드 시각화
11.7.2 알고리즘 특성¶
- 시간 복잡도 \(O(n \log n)\), 비적응형 정렬: 힙 구성에는 \(O(n)\) 시간이 걸린다. 힙에서 최댓값을 꺼내는 시간 복잡도는 \(O(\log n)\)이며, 총 \(n - 1\) 회 반복한다.
- 공간 복잡도 \(O(1)\), 제자리 정렬: 몇 개의 포인터 변수가 \(O(1)\) 공간을 사용한다. 원소 교환과 힙 재정렬은 모두 원래 배열에서 수행한다.
- 불안정 정렬: 힙의 루트 원소와 끝 원소를 교환할 때 값이 같은 원소들의 상대적 위치가 바뀔 수 있다.