힙 정렬(Heap Sort)의 원리와 구현 - soo:bak

작성일 : 2025년 10월 26일

힙 정렬이란?

정렬되지 않은 배열 [5, 3, 8, 4, 9, 1, 6, 2, 7]이 있을 때, 이를 정렬하는 방법은 여러 가지가 있습니다.

원소를 하나씩 비교할 수도 있고, 분할하여 정렬할 수도 있습니다.

여러가지 정렬 방법들 중, 힙 정렬(Heap Sort)은 힙(Heap) 자료구조를 이용한 정렬 방법입니다.

힙은 완전 이진 트리의 일종으로, 부모 노드가 항상 자식 노드보다 크거나 작은 값을 가지는 특성이 있습니다.

이러한 힙의 특성을 활용하여 배열을 정렬하는 방식으로 동작합니다.

힙의 개념

힙 정렬을 이해하기 위해서는 먼저 힙 자료구조를 알아야 합니다.

힙(Heap)은 다음 조건을 만족하는 완전 이진 트리입니다:

완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워짐
힙 속성: 부모 노드와 자식 노드 간의 대소 관계가 일정함

힙은 크게 두 종류가 있습니다:

최대 힙(Max Heap): 부모 노드가 항상 자식 노드보다 큰 값을 가짐

최소 힙(Min Heap): 부모 노드가 항상 자식 노드보다 작은 값을 가짐

힙 정렬에서는 일반적으로 최대 힙을 사용하여 오름차순 정렬을 수행합니다.

참고: 최대 힙(Max Heap)과 우선순위 큐의 원리와 구현 - soo:bak

힙의 배열 표현

힙은 트리 구조지만, 완전 이진 트리이기 때문에 배열을 통해 효율적으로 표현할 수 있습니다.

인덱스 i에 대해:

부모 노드: (i - 1) / 2
왼쪽 자식: 2 * i + 1
오른쪽 자식: 2 * i + 2

예를 들어, 배열 [9, 7, 6, 4, 5, 2, 3]은 다음과 같은 최대 힙을 나타냅니다:

인덱스:  0  1  2  3  4  5  6
값:      9  7  6  4  5  2  3

       9(0)
      /    \
    7(1)   6(2)
    / \    / \
  4(3) 5(4) 2(5) 3(6)

힙 정렬의 원리

힙 정렬은 다음과 같은 과정으로 동작합니다:

힙 구성: 주어진 배열을 최대 힙으로 변환
최댓값 추출: 힙의 루트(최댓값)를 배열의 마지막 원소와 교환
힙 크기 감소: 마지막 원소를 제외하고 힙 크기를 하나 줄임
힙 재구성: 루트에서 시작하여 힙 속성을 복구
반복: 힙에 원소가 하나 남을 때까지 2~4번 과정 반복

단계별 예시

배열 [4, 10, 3, 5, 1]을 힙 정렬하는 과정입니다:

1단계: 최대 힙 구성

초기: [4, 10, 3, 5, 1]

힙 구성: [10, 5, 3, 4, 1]

2단계: 루트(10)와 마지막 원소(1) 교환

[1, 5, 3, 4, 10]
힙 크기: 4 (10은 제외)

3단계: 힙 재구성

[5, 4, 3, 1, 10]

4단계: 루트(5)와 마지막 원소(1) 교환

[1, 4, 3, 5, 10]
힙 크기: 3

5단계: 계속 반복

[4, 1, 3, 5, 10]
[3, 1, 4, 5, 10]
[1, 3, 4, 5, 10]

최종: [1, 3, 4, 5, 10]

Heapify 연산

Heapify는 특정 노드를 루트로 하는 서브트리를 힙 속성을 만족하도록 재구성하는 연산입니다.

동작 과정

주어진 노드 i에 대해:

왼쪽 자식, 오른쪽 자식, 현재 노드 중 가장 큰 값을 찾음
가장 큰 값이 현재 노드가 아니면 교환
교환된 자식 노드에서 재귀적으로 heapify 수행

Heapify 구현

void heapify(vector<int>& arr, int n, int i) {
  int largest = i;  // 현재 노드를 largest로 초기화
  int left = 2 * i + 1;  // 왼쪽 자식
  int right = 2 * i + 2;  // 오른쪽 자식
  
  // 왼쪽 자식이 현재 노드보다 크면
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }
  
  // 오른쪽 자식이 현재 가장 큰 값보다 크면
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }
  
  // largest가 현재 노드가 아니면 교환 후 재귀
  if (largest != i) {
    swap(arr[i], arr[largest]);
    heapify(arr, n, largest);
  }
}

핵심:

n은 힙의 크기 (정렬 과정에서 점차 감소)
i는 heapify를 수행할 노드의 인덱스
부모와 자식 중 가장 큰 값을 루트로 이동
교환이 발생하면 재귀적으로 하위 서브트리도 heapify

구현

기본 구현

#include <bits/stdc++.h>
using namespace std;

void heapify(vector<int>& arr, int n, int i) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;
  
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }
  
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }
  
  if (largest != i) {
    swap(arr[i], arr[largest]);
    heapify(arr, n, largest);
  }
}

void heapSort(vector<int>& arr) {
  int n = arr.size();
  
  // 1단계: 최대 힙 구성
  // 마지막 비단말 노드부터 역순으로 heapify
  for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
  
  // 2단계: 하나씩 추출하며 정렬
  for (int i = n - 1; i > 0; i--) {
    // 루트(최댓값)를 마지막 원소와 교환
    swap(arr[0], arr[i]);
    
    // 힙 크기를 줄이고 루트에서 heapify
    heapify(arr, i, 0);
  }
}

int main() {
  vector<int> arr = {5, 3, 8, 4, 9, 1, 6, 2, 7};
  
  heapSort(arr);
  
  for (int x : arr) cout << x << " ";
  cout << "\n";
  
  return 0;
}

구현 설명:

힙 구성: n/2 - 1부터 0까지 역순으로 heapify를 수행하여 최대 힙을 구성
- 리프 노드는 이미 힙 속성을 만족하므로 비단말 노드부터 시작
정렬: 루트와 마지막 원소를 교환한 후, 힙 크기를 줄이고 루트에서 heapify
- 교환된 최댓값은 정렬된 위치에 고정
- 남은 부분에 대해 힙 속성 복구

반복문 기반 Heapify

재귀 대신 반복문으로 heapify를 구현할 수도 있습니다.

void heapifyIterative(vector<int>& arr, int n, int i) {
  while (true) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest]) {
      largest = left;
    }
    
    if (right < n && arr[right] > arr[largest]) {
      largest = right;
    }
    
    if (largest == i) break;  // 힙 속성 만족
    
    swap(arr[i], arr[largest]);
    i = largest;  // 다음 위치로 이동
  }
}

장점:

재귀 호출 스택 사용하지 않음
깊은 트리에서도 스택 오버플로우 위험 없음

시간 복잡도

힙 정렬의 시간 복잡도는 다음과 같습니다.

모든 경우 시간 복잡도: \(O(n \log n)\)

힙 정렬은 최선, 평균, 최악의 경우 모두 \(O(n \log n)\)의 시간 복잡도를 가집니다.

힙 구성: \(O(n)\)

비단말 노드는 \(n/2\)개
각 노드에서 heapify 수행
전체적으로 \(O(n)\)

정렬 과정: \(O(n \log n)\)

\(n\)번의 반복
각 반복마다 heapify 수행 (\(O(\log n)\))
전체: \(n \times O(\log n) = O(n \log n)\)

전체: \(O(n) + O(n \log n) = O(n \log n)\)

이는 빠른 정렬의 평균 성능과 같지만, 최악의 경우에도 \(O(n \log n)\)을 보장한다는 장점이 있습니다.

공간 복잡도

제자리 정렬: \(O(1)\)
추가 배열이 필요 없음
재귀 구현 시 호출 스택: \(O(\log n)\) (트리의 높이)

힙 정렬의 특징

장점

최악의 경우 보장: 모든 경우에 \(O(n \log n)\) 시간 복잡도 보장
제자리 정렬: 추가 메모리가 거의 필요하지 않음
단순한 구조: 구현이 비교적 간단하고 이해하기 쉬움

단점

불안정 정렬: 같은 값을 가진 원소들의 상대적 순서가 보장되지 않음
캐시 효율성 낮음: 힙 연산은 메모리를 불연속적으로 접근하여 캐시 미스가 많음
실전 성능: 평균적으로 빠른 정렬보다 느림

다른 정렬과 비교

특성	힙 정렬	빠른 정렬	병합 정렬
평균 시간 복잡도	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n \log n)\)
최악 시간 복잡도	\(O(n \log n)\)	\(O(n^2)\)	\(O(n \log n)\)
공간 복잡도	\(O(1)\)	\(O(\log n)\)	\(O(n)\)
안정성	불안정	불안정	안정
제자리 정렬	O	O	X
실전 성능	보통	빠름	빠름

힙 정렬은 최악의 경우 성능을 보장해야 하는 상황에서 유용하며, 메모리가 제한적인 환경에서도 효과적입니다.

힙 자료구조의 활용

힙은 정렬뿐만 아니라 다양한 상황에서 활용됩니다.

1. 우선순위 큐

힙은 우선순위 큐의 효율적인 구현 방법입니다.

삽입: \(O(\log n)\)
최댓값/최솟값 추출: \(O(\log n)\)
최댓값/최솟값 조회: \(O(1)\)

priority_queue<int> maxHeap;  // 최대 힙 (기본)
priority_queue<int, vector<int>, greater<int>> minHeap;  // 최소 힙

참고: 최대 힙(Max Heap)과 우선순위 큐의 원리와 구현 - soo:bak

2. K번째 큰 원소 찾기

크기 K의 최소 힙을 유지하면서 배열을 순회하면, K번째 큰 원소를 효율적으로 찾을 수 있습니다.

int findKthLargest(vector<int>& arr, int k) {
  priority_queue<int, vector<int>, greater<int>> minHeap;
  
  for (int num : arr) {
    minHeap.push(num);
    if (minHeap.size() > k) {
      minHeap.pop();
    }
  }
  
  return minHeap.top();
}

시간 복잡도: \(O(n \log k)\)

3. 힙을 이용한 중간값 찾기

최대 힙과 최소 힙을 함께 사용하면 스트리밍 데이터에서 중간값을 효율적으로 유지할 수 있습니다.

최대 힙: 작은 절반의 원소 저장
최소 힙: 큰 절반의 원소 저장

4. 다익스트라 최단 경로

다익스트라 알고리듬은 우선순위 큐(힙)를 사용하여 최단 거리를 효율적으로 계산합니다.

각 단계에서 최소 거리 정점을 \(O(\log n)\)에 추출할 수 있습니다.

힙 구성 최적화

힙을 구성하는 방법에는 두 가지 접근이 있습니다.

상향식 구성 (Bottom-up)

빈 힙에 원소를 하나씩 삽입하는 방법입니다.

void buildHeapBottomUp(vector<int>& arr) {
  for (int i = 1; i < arr.size(); i++) {
    int child = i;
    while (child > 0) {
      int parent = (child - 1) / 2;
      if (arr[child] > arr[parent]) {
        swap(arr[child], arr[parent]);
        child = parent;
      } else {
        break;
      }
    }
  }
}

시간 복잡도: \(O(n \log n)\)

하향식 구성 (Top-down)

마지막 비단말 노드부터 heapify를 수행하는 방법입니다 (기본 구현에서 사용).

void buildHeapTopDown(vector<int>& arr) {
  int n = arr.size();
  for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
}

시간 복잡도: \(O(n)\)

하향식 구성이 상향식보다 점근적으로 빠르므로, 일반적으로 하향식 방법을 사용합니다.

실전 예제: K개의 가장 큰 수 찾기

문제

배열에서 K번째로 큰 수를 찾는 프로그램을 작성하시오.

입력: 정수 배열과 K
출력: K번째로 큰 수

접근법

크기 K의 최소 힙을 유지
배열을 순회하며 힙에 원소 추가
힙 크기가 K를 초과하면 최솟값 제거
최종적으로 힙의 루트가 K번째 큰 수

구현

#include <bits/stdc++.h>
using namespace std;

int findKthLargest(vector<int>& arr, int k) {
  // 최소 힙 사용
  priority_queue<int, vector<int>, greater<int>> minHeap;
  
  for (int num : arr) {
    minHeap.push(num);
    
    // 힙 크기가 k를 초과하면 최솟값 제거
    if (minHeap.size() > k) {
      minHeap.pop();
    }
  }
  
  // 힙의 루트가 k번째로 큰 수
  return minHeap.top();
}

int main() {
  vector<int> arr = {3, 2, 1, 5, 6, 4};
  int k = 2;
  
  cout << "K번째 큰 수: " << findKthLargest(arr, k) << "\n";
  // 출력: 5
  
  return 0;
}

시간 복잡도: \(O(n \log k)\)

공간 복잡도: \(O(k)\)

이 방법은 \(n\)이 매우 크고 \(k\)가 작을 때 효율적입니다.

C++ STL의 힙 함수

C++ 표준 라이브러리는 <algorithm> 헤더에서 힙 관련 함수를 제공합니다.

make_heap

배열을 힙으로 변환합니다.

vector<int> arr = {4, 10, 3, 5, 1};
make_heap(arr.begin(), arr.end());  // 최대 힙 구성

push_heap

힙에 원소를 추가합니다.

arr.push_back(15);
push_heap(arr.begin(), arr.end());

pop_heap

힙에서 최댓값을 제거합니다.

pop_heap(arr.begin(), arr.end());  // 최댓값을 배열 끝으로 이동
arr.pop_back();  // 실제 제거

sort_heap

힙을 정렬된 배열로 변환합니다.

sort_heap(arr.begin(), arr.end());

이러한 함수들을 사용하면 힙 정렬을 간단히 구현할 수 있습니다:

void heapSortSTL(vector<int>& arr) {
  make_heap(arr.begin(), arr.end());
  sort_heap(arr.begin(), arr.end());
}

마무리

힙 정렬은 완전 이진 트리 기반의 힙 자료구조를 이용한 정렬 알고리듬입니다.

모든 경우에 \(O(n \log n)\)의 시간 복잡도를 보장하며, 추가 메모리가 거의 필요 없는 제자리 정렬입니다.

빠른 정렬의 평균 성능에는 미치지 못하지만, 최악의 경우에도 안정적인 성능을 보장한다는 장점이 있습니다.

힙 구성은 하향식으로 \(O(n)\)에 수행하고, 정렬 과정에서 \(n\)번의 heapify 연산을 통해 정렬을 완성합니다.

각 heapify 연산은 \(O(\log n)\) 시간이 소요되므로, 전체 시간 복잡도는 \(O(n \log n)\)입니다.

힙은 정렬뿐만 아니라 우선순위 큐, K번째 원소 찾기, 다익스트라 알고리듬 등 다양한 분야에서 활용되는 중요한 자료구조입니다.

관련 글:

관련 문제: