힙 정렬 (Heap Sort)

2026. 07. 25

들어가는 말

힙 정렬은 힙 자료구조의 속성을 이용해 배열을 정렬하는 알고리즘이다.
힙은 완전 이진 트리 형태로 구성되며 부모와 자식 사이에 일정한 대소 관계를 유지한다.
오름차순 정렬에서는 부모가 자식보다 크거나 같은 최대 힙을 사용한다.
최대 힙의 루트에는 항상 최댓값이 있으므로 해당 원소를 미정렬 구간의 맨 뒤로 보내 위치를 확정한다.
교환으로 깨진 힙 구조를 복구한 뒤 같은 작업을 반복하면 배열의 오른쪽부터 큰 값이 차례로 자리 잡아 오름차순 정렬이 완성된다.
시간 복잡도는 항상 O(n log n)이며 별도의 배열이 필요하지 않다.
다만 같은 값을 가진 원소의 순서가 유지되지 않는 불안정 정렬이다.

힙의 배열 표현

힙은 완전 이진 트리 구조를 가지므로 각 노드를 배열에 빈자리 없이 저장할 수 있다.
이 글에서는 배열의 0번 인덱스부터 원소를 차례대로 저장하므로 루트 노드의 인덱스는 0이다.
힙에 저장된 원소의 개수를 n이라고 하면 각 노드의 인덱스 i는 0부터 n - 1까지이다.

관계	인덱스
부모	`(i - 1) / 2`
왼쪽 자식	`2 * i + 1`
오른쪽 자식	`2 * i + 2`

인덱스가 i = 0인 루트 노드는 부모가 없으므로 부모 인덱스 공식은 i > 0인 노드에만 적용된다.

오름차순 정렬 과정 살펴보기

Array  [ 4 9 3 5 1 ]
Index    0 1 2 3 4

         4
        [0]
       /   \
     9      3
    [1]    [2]
    / \
   5   1
  [3] [4]

먼저 배열 전체를 최대 힙으로 만든다.
각 부모 노드를 자식들과 비교하고, 가장 큰 자식이 부모보다 크면 두 노드를 교환한다.
교환으로 아래로 내려간 값이 그 위치의 자식보다 작을 수 있으므로 최대 힙 조건을 만족할 때까지 비교를 반복한다.

자식을 하나 이상 가진 부모 노드의 개수는 array_size / 2이고, 마지막 부모 노드의 인덱스는 array_size / 2 - 1이다.
원소가 5개인 경우 부모 노드는 2개이며, array[0]과 array[1]에 위치한다.
두 위치에 저장된 값은 각각 4와 9이다.
최대 힙은 마지막 부모 노드부터 루트 방향으로 올라가며 구성한다.
아래쪽 서브트리를 먼저 최대 힙으로 만들어야 상위 노드에서 부모와 두 자식 중 가장 큰 값을 올바르게 선택할 수 있기 때문이다.

단계	확인하는 노드	판단	결과
최대 힙 구성 전	-	-	`4 9 3 5 1`
인덱스 `1` 확인	`9`와 자식 `5 1`	부모가 두 자식보다 크므로 유지	`4 9 3 5 1`
인덱스 `0` 확인	`4`와 자식 `9 3`	부모 `4`와 가장 큰 자식 `9`를 교환	`9 4 3 5 1`
인덱스 `1` 재확인	`4`와 자식 `5 1`	부모 `4`와 가장 큰 자식 `5`를 교환	`9 5 3 4 1`

이 과정을 거치면 다음과 같은 최대 힙이 완성된다.

Array  [ 9 5 3 4 1 ]
Index    0 1 2 3 4

         9
        [0]
       /   \
     5       3
    [1]    [2]
    / \
   4   1
  [3] [4]

이제 최대 힙을 이용해 정렬을 수행한다.
먼저 루트에 있는 최댓값과 미정렬 구간의 마지막 값을 교환해 최댓값을 맨 뒤로 보낸다.
교환 후에는 루트로 옮겨진 값이 최대 힙 조건을 위반할 수 있으므로 미정렬 구간을 다시 최대 힙으로 구성한다.
이 과정을 반복하면 모든 원소의 위치가 확정되어 정렬이 완성된다.

표에서 │의 왼쪽은 최대 힙으로 다시 구성해야 하는 미정렬 구간이고, 오른쪽은 위치가 확정된 정렬 완료 구간이다.

단계	교환 후	재구성 후	새로 확정되는 값
시작 전	-	`9 5 3 4 1 │`	-
1회차	`1 5 3 4 │ 9`	`5 4 3 1 │ 9`	`9`
2회차	`1 4 3 │ 5 9`	`4 1 3 │ 5 9`	`5`
3회차	`3 1 │ 4 5 9`	`3 1 │ 4 5 9`	`4`
4회차	`1 │ 3 4 5 9`	재구성 불필요	`3`

한 회차가 끝날 때마다 최댓값 하나가 정렬 완료 구간의 맨 앞에 추가된다.
원소 5개 중 4개의 자리가 확정되면 나머지 1개의 자리도 자연스럽게 확정되므로 정렬이 끝난다.

시간 복잡도

먼저 배열을 최대 힙으로 만드는 데 O(n)이 걸린다.
이후 루트의 최댓값을 미정렬 구간의 마지막 원소와 교환하면 최댓값의 자리가 확정된다.
교환 후에는 남은 미정렬 구간의 최대 힙 구조를 복구하는 데 O(log n)이 걸린다.
이 과정을 n - 1번 반복하므로 전체 시간 복잡도는 O(n log n)이다.
배열이 이미 정렬되어 있더라도 같은 과정을 반복하므로 최선, 평균, 최악의 시간 복잡도는 모두 O(n log n)이다.

소스 코드

#include <stdio.h>

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int arr[], int size, int root)
{
    while (1)
    {
        int largest = root;
        int left = 2 * root + 1;
        int right = 2 * root + 2;

        if (left < size && arr[left] > arr[largest])
            largest = left;

        if (right < size && arr[right] > arr[largest])
            largest = right;

        if (largest == root)
            break;

        swap(&arr[root], &arr[largest]);
        root = largest;
    }
}

void build_max_heap(int arr[], int size)
{
    for (int i = size / 2 - 1; i >= 0; i--)
        heapify(arr, size, i);
}

void heap_sort(int arr[], int size)
{
    build_max_heap(arr, size);

    for (int heap_end = size - 1; heap_end > 0; heap_end--)
    {
        swap(&arr[0], &arr[heap_end]);
        heapify(arr, heap_end, 0);
    }
}

int main(void)
{
    int arr[] = { 4, 9, 3, 5, 1 };
    int size = sizeof(arr) / sizeof(arr[0]);

    heap_sort(arr, size);

    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]); // Result: 1 3 4 5 9

    return 0;
}

구현 설명

build_max_heap 함수는 자식이 있는 마지막 노드인 size / 2 - 1부터 루트까지 역순으로 heapify를 호출해 배열 전체를 최대 힙으로 만든다.

heapify 함수는 root와 두 자식 가운데 가장 큰 값의 인덱스를 largest에 저장한다.
가장 큰 값이 root에 있으면 최대 힙 조건을 만족하므로 반복을 끝낸다.
자식이 더 크면 부모와 해당 자식을 교환하고, 교환된 자식의 위치에서 다시 최대 힙 조건을 확인한다.

heap_sort 함수는 build_max_heap으로 구성한 최대 힙을 이용해 정렬을 수행한다.
루트에 있는 최댓값을 미정렬 구간의 마지막 원소와 교환해 위치를 확정한다.
이후 힙의 크기를 1씩 줄이면서 남은 미정렬 구간에 heapify를 적용하고, 같은 과정을 반복한다.