[알고리즘] 효율적인 '자료구조 기반' 정렬(N log₂N): 힙 정렬(Heap Sort)

 

0. 힙 정렬(Heap Sort)

힙 정렬은 힙(Heap) 자료구조를 이용해 배열을 정렬하는 알고리즘이다.

• 힙은 완전 이진 트리 형태로, 최대 힙(Max Heap)을 사용하면 항상 루트가 가장 큰 값을 가지게 된다.
• 힙 정렬(Heap Sort) 은 이 성질을 이용해 배열을 정렬한다.

 

0-1. 힙(Heap)이란?

완전 이진 트리(Complete Binary Tree) 형태의 자료구조.

 

• 부모와 자식 노드 사이에 힙 속성을 만족:
  • 최대 힙(Max Heap): 부모 ≥ 자식 → 루트가 항상 최댓값
  • 최소 힙(Min Heap): 부모 ≤ 자식 → 루트가 항상 최솟값
• 보통 배열로 구현 : 부모/자식 인덱스 계산이 간단
  • 부모: i  →  자식: 2i+1 , 2i+2

 

 

0-2. 힙 정렬(Heap Sort)의 아이디어

1. 배열을 최대 힙(Max Heap)으로 만든다. (루트가 최댓값 되도록)
2. 루트(최댓값)를 배열의 맨 뒤로 이동 (정렬 완료 영역으로 이동). 
3. 남은 배열들끼리 다시 힙 속성을 유지하도록 정리.
4. 위 과정을 반복하여 배열을 정렬.

결과적으로 오름차순 정렬이 된다.

힙 정렬 = 루트(최댓값) 잡기 → 끝으로 보내기 → 남은 배열 다시 힙 만들기 반복

 

 

0-3. 힙 정렬(Heap Sort) 단계별 예시

예시 배열 : [ 4, 10, 3, 5, 1 ]

 

 

Step 1. 최대 힙 만들기

부모 ≥ 자식 되도록 배열을 트리 구조로 재배치

 

• 배열 형태: [10, 5, 3, 4, 1]
• 루트가 최댓값 10인 것을 확인

 

 

 

Step 2. 루트(10)와 마지막 원소(1) 교환

가장 큰 값을 정렬된 위치로 보냄

 

• 배열: [1, 5, 3, 4, 10]
• 이제 10은 정렬 완료 영역으로 이동

 

 

Step 3. 남은 배열 힙 재정렬

[1, 5, 3, 4]를 최대 힙으로 다시 구성

• 배열: [5, 4, 3, 1, 10]

 

 

Step 4. 루트(5) ↔ 마지막 원소(1) 교환

 

• 배열: [1, 4, 3, 5, 10]
• 힙 재정렬 → [4, 1, 3, 5, 10]
• 정렬 완료 영역: [5, 10]

 

 

 

Step 5. 반복 

 

• 루트 ↔ 마지막 남은 원소 교환 후 힙 재정렬
• 최종 배열: [1, 3, 4, 5, 10] → 오름차순 정렬 완료

 

 

 

1. 제자리 정렬(In-place sort)이란?

추가적인 메모리를 거의 사용하지 않고(O(1) ~ O(log n))

주어진 배열 내부에서만 원소들의 위치를 바꿔가며 정렬하는 알고리즘.

• 예시 : 선택 정렬, 삽입 정렬, 퀵 정렬(일반 구현), 힙 정렬
• 반례 : 병합 정렬(추가로 O(n) 메모리 필요)

힙 정렬은 배열을 그대로 힙처럼 사용하기 때문에 추가 메모리 없이 정렬 가능

 

 

 

2. 퀵 정렬, 병합 정렬과의 차이

알고리즘	메모리	정렬 안정성	평균 시간 복잡도	최악 시간 복잡도
퀵 정렬	제자리(O(log n) 스택)	불안정	O(n log n)	O(n²)
병합 정렬	추가 O(n) 필요	안정	O(n log n)	O(n log n)
힙 정렬	제자리(O(1))	불안정	O(n log n)	O(n log n)

힙 정렬의 특징은 추가 메모리 거의 필요 없음 + 항상 O(n log n) 보장이지만, 퀵/병합 정렬보다 실제 실행 속도는 느린 편.

 

 

 

3. 재귀 호출을 사용한 정렬은 제자리 정렬인가?

재귀를 사용한다고 해서 무조건 제자리 정렬이 아닌 건 아님

중요한 건 스택 프레임의 사용량과 추가 메모리 필요 여부

• 퀵 정렬 : 재귀 호출을 사용하지만, 추가 메모리는 O(log n)이므로 제자리 정렬로 본다.
• 병합 정렬 : 재귀 호출 + O(n) 보조 배열이 필요 → 제자리 정렬 아님.

 

 

4. 힙 정렬의 시간 복잡도

• 최선: O(n log n)
• 평균: O(n log n)
• 최악: O(n log n)

항상 일정한 성능을 보장. (퀵 정렬처럼 O(n²)로 떨어지지 않음)

 

 

 

5. 특정 상황에서의 활용 예

• 메모리 제약이 있는 환경
  • 힙 정렬은 제자리 정렬(In-place sort)이므로 추가 배열이 거의 필요 없다. 
    • → 메모리가 제한된 시스템이나 임베디드 환경에서 유리
• 최악 성능 보장이 필요한 경우
  • 퀵 정렬과 달리, 힙 정렬은 항상 O(n log n)의 성능을 보장한다.
    • → 최악 케이스에서도 실행 시간이 크게 늘어나면 안 되는 상황에 적합
• 정렬이 필요하지만 우선순위 기반 처리가 중요한 경우
  • 힙 구조를 기반으로 최댓값/최솟값을 빠르게 추출할 수 있다.
    • → 정렬 목적보다는 우선순위 큐 구현이나 작업 스케줄링 등 동적 데이터 처리에도 활용 가능
• 대규모 데이터 정렬 시 보조 메모리 제한
  • 병합 정렬처럼 O(n) 크기의 추가 배열을 쓰지 않으면서 정렬 가능
    • → 외부 메모리(디스크 등)에 데이터를 임시 저장하지 않고도 처리 가능

 

 

6. 우선순위 큐와 힙 정렬의 차이

구분	힙 정렬(Heap Sort)	우선순위 큐(Priority Queue)
목적	전체 배열을 정렬하는 과정	정렬 목적 아님, 가장 높은/낮은 값만 빠르게 꺼내기
자료구조	힙 활용	힙 활용
연산	모든 원소 꺼내기 + Heapify: O(n log n)	삽입/삭제: O(log n)
메모리	제자리 정렬, 추가 메모리 거의 없음	동적 데이터 처리 가능, 힙 유지 필요
특징	제자리 정렬, 최악 케이스 O(n log n) 보장, 퀵/병합 정렬보다 메모리 효율적, 실행 속도는 다소 느림	동적 처리에 적합, 최대/최소값 빠르게 추출 가능
활용 상황	메모리 제한, 최악 성능 보장 필요 상황	실시간 우선순위 처리, 동적 데이터 관리

 

힙 정렬         = 힙의 전체 활용
우선순위 큐  = 힙의 동적 활용