O(n²) 너머 ②: 제자리 정렬의 해답, 힙 정렬(Heap Sort)

🚀 들어가며: 가장 중요한 데이터, 어떻게 항상 맨 앞에 둘 수 있을까?

지난번 글에서 병합 정렬을 통해 '분할 정복'이라는 강력한 무기로 $O(n^2)$의 벽을 넘는 법을 다뤘다.

 

병합 정렬은 전체를 정렬하는 아주 효율적인 방법이다.

 

https://upcurvewave.tistory.com/789

O(n²)의 벽을 넘어서기 위한 관문, 병합 정렬

 

 

그런데 잠시 다른 질문을 던져보면 어떨까?

 

"전체 리스트를 매번 정렬하는 게 아니라,
그저 '가장 중요한 데이터 1개'만 계속해서 빠르게 뽑아내고 싶다면
어떻게 해야 할까?"

마치 수많은 작업 요청 중에 가장 긴급한 건을 즉시 처리하거나, 실시간 게임 랭킹에서 1위 유저를 바로바로 화면에 보여줘야 하는 상황처럼 말이다. 매번 전체를 sort()하기에는 너무 비효율적이지 않을까?

 

바로 이 질문, '우선순위가 가장 높은 데이터를 효율적으로 관리하는 방법'에 대한 아주 똑똑한 해답이 바로 힙(Heap)이라는 자료구조다.

 

힙은 그 구조 자체가 '대장(가장 크거나 작은 값)'을 항상 루트, 즉 맨 꼭대기에 위치시키도록 설계되었다.

 

그리고 힙 정렬은 이 영리한 자료구조의 특징을 아주 창의적으로 활용한 알고리즘이다.

 

이번 글에는 "힙 정렬은 빠르다"는 결론에서 시작하는 대신, 다음과 같은 질문들을 함께 파고들며 그 본질을 이해해 보고자 한다.

• 질문 1: 힙(Heap)은 어떤 특별한 규칙으로 데이터를 관리하기에 '대장'을 항상 식별할 수 있을까?
• 질문 2: '대장'을 계속 뽑아내는 이 방식이 어떻게 전체 데이터를 정렬하는 결과로 이어질까?
• 질문 3: 병합 정렬이 추가 공간($O(n)$)을 썼다면, 힙 정렬은 시간과 공간의 트레이드오프를 어떻게 했을까?
  
  
  

---

힙(Heap)이란 무엇일까?

먼저 힙이 무엇일까?

 

힙(Heap)은 최댓값 및 최솟값을 빠르게 찾아내기 위해 고안된 완전 이진 트리(Complete Binary Tree) 기반의 자료구조다.

 

논리적으로는 완전 이진 트리(Complete Binary Tree) 형태를 가지지만 물리적으로는 배열을 사용해 매우 효율적으로 구현된다.

 

 

힙은 흔히 '우선순위 큐(Priority Queue)'를 구현하는 핵심 엔진으로 알려져 있다. 데이터가 삽입되거나 삭제될 때마다 정해진 규칙에 따라 스스로를 재정렬하여, 우선순위가 가장 높은 요소를 항상 트리의 꼭대기, 즉 배열의 첫 번째 원소에 위치시킨다.

 

이 '정해진 규칙'이 바로 힙의 핵심이며, 어떻게 힙이 효율적으로 동작하는지를 이해하는 열쇠이다. 이제 힙을 지탱하는 두 가지 핵심 규칙을 살펴보며 첫 번째 질문에 대한 답을 본격적으로 찾아보자.

🤔 질문 1: 힙(Heap)은 어떤 규칙으로 '대장'을 식별할까?

힙이 '대장'을 항상 꼭대기에 둘 수 있는 비결은, 아주 단순하지만 강력한 두 가지 규칙을 엄격하게 지키기 때문이다.

규칙 1: 부모와 자식 간의 대소 관계 (힙 속성)

힙의 첫 번째 규칙은 부모 노드와 자식 노드 간의 값 크기를 명확히 정의하는 것이다. 이 규칙에 따라 힙은 두 종류로 나뉜다.

• 최대 힙 (Max Heap): 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같다. 이 규칙을 따르면, 가장 큰 값은 자식으로 내려갈 수 없으므로 자연스럽게 트리 꼭대기인 루트(Root)에 위치한다.
• 최소 힙 (Min Heap): 부모 노드의 값은 항상 자식 노드의 값보다 작거나 같다. 반대로 가장 작은 값이 항상 루트에 위치하게 된다.

이처럼 '대장'의 자격(최댓값 또는 최솟값)을 규칙으로 정해두었기 때문에, 우리는 힙의 루트 노드만 확인하면 $O(1)$의 시간 복잡도로 전체 데이터의 최댓값 혹은 최솟값을 즉시 알 수 있다.

 

규칙 2: 데이터를 쌓는 순서 (구조적 속성)

힙의 두 번째 규칙은 트리의 모양에 관한 것이다. 힙은 반드시 완전 이진 트리(Complete Binary Tree)의 형태를 유지해야 한다.

 

완전 이진 트리란, 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드들은 왼쪽부터 순서대로 채워지는 트리를 말한다. 중간에 빈자리가 생기는 것을 허용하지 않는다.

 

 

 

 

이 구조적 규칙이 중요한 이유는, 힙을 배열(Array)만으로 아주 효율적으로 구현할 수 있게 해주기 때문이다. 노드에 빈틈이 없으므로 배열의 인덱스를 통해 부모와 자식 노드의 위치를 간단한 계산으로 찾아낼 수 있다. 이는 힙 정렬이 추가적인 메모리 낭비를 줄이는 데 결정적인 역할을 한다.

 

그런데 여기서 궁금한 점이 생긴다. 배열 인덱스만으로 어떻게 부모와 자식 노드의 위치를 바로 계산할 수 있을까?

 

배열의 인덱스가 i인 노드를 기준으로 부모와 자식 노드의 인덱스는 간단한 수식으로 바로 찾을 수 있다.
(배열 인덱스가 0부터 시작할 경우)

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

 

이처럼 완전 이진 트리는 구조적으로 예측 가능하기에, 포인터나 참조 없이 단순한 산술 연산만으로 트리 구조를 탐색할 수 있다. 이것이 바로 힙을 배열로 구현했을 때의 효율성이 나오는 지점이다.

 

https://renechoi.github.io/web-view/blog-contents/algorithm/heap-ds/

완전 이진 트리와 배열 인덱스 관계

 

결국 힙이란, '모양 규칙(완전 이진 트리)'을 만족하는 트리 구조 위에서, '부모-자식 간 대소 관계 규칙'을 지키는 자료구조인 셈이다. 이 두 가지 규칙의 조합이 '대장'을 항상 꼭대기에 두는 효율적인 시스템을 완성한다.

 

이제 첫 번째 질문에 대한 답을 얻었다. 다음으로는 이 원리를 이용해 어떻게 전체 배열을 정렬하는지, 두 번째 질문에 대한 답을 찾아보자.

---

🧐 질문 2: '대장'을 뽑는 방식이 어떻게 정렬로 이어질까?

'대장'을 한 번에 식별할 수 있다는 힙의 특성은 그 자체로도 강력하지만, 이 과정을 반복하면 전체 데이터를 정렬하는 멋진 알고리즘으로 발전한다. 이것이 바로 힙 정렬(Heap Sort)의 핵심 아이디어다.

 

힙 정렬의 과정은 크게 두 단계로 나눌 수 있다. (오름차순 정렬을 위해 최대 힙을 사용한다고 가정하자.)

1단계: 힙 구성 (Heapify)

먼저, 정렬되지 않은 초기 배열 전체를 최대 힙으로 만들어야 한다. 이 과정을 '힙 구성(Heapify)'이라고 부른다.

• 배열의 모든 요소를 힙의 규칙에 맞게 재배치하여, 가장 큰 '대장' 요소가 배열의 첫 번째 위치(루트)에 오도록 만든다.
• 이 과정이 끝나면, 배열은 논리적으로 완전한 최대 힙 구조를 갖게 된다.

2단계: 정렬 (Sorting)

이제 본격적인 정렬 단계다. 힙의 '대장'을 이용해 배열을 뒤에서부터 차곡차곡 채워나간다.

1. '대장'을 맨 뒤로 보내기: 현재 힙의 루트(배열의 첫 번째 요소)에 있는 최댓값과 힙의 가장 마지막 요소를 맞바꾼다.
2. 정렬 완료 처리: 이제 배열의 가장 마지막 위치에는 최댓값이 확정되었다. 이 위치는 더 이상 힙의 일부가 아닌, 정렬이 완료된 영역으로 취급한다. 즉, 힙의 크기가 1 줄어든다.
3. 힙 재구성: '대장'이 있던 루트 자리에는 원래 마지막에 있던 작은 값이 올라와 힙의 규칙을 깨뜨렸을 것이다. 이 새로운 루트를 시작으로 힙의 규칙을 복원(Down-Heap)하여, 남은 요소 중 가장 큰 값이 다시 루트로 올라오도록 한다.
4. 반복: 힙에 남은 요소가 하나가 될 때까지 위 1~3번 과정을 반복한다.

이 과정을 거치면, 가장 큰 값부터 순서대로 배열의 맨 뒤부터 채워지므로 최종적으로 오름차순으로 정렬된 배열을 얻게 된다.

 

 

결론적으로, '대장을 뽑아 맨 뒤로 보내는' 행위를 반복하는 것만으로 전체 데이터가 자연스럽게 정렬되는 것이다. 이는 힙이라는 자료구조가 가진 '최대/최소값 보장'이라는 강력한 특성을 정렬 문제에 절묘하게 적용한 결과다.

 

이제 우리는 힙 정렬의 동작 원리까지 파악했다. 마지막으로 병합 정렬과의 비교를 통해 힙 정렬의 실용적인 장단점을 분석해 보자.

---

⚖️ 질문 3: 병합 정렬과 비교한 힙 정렬의 트레이드오프

병합 정렬의 가장 큰 특징 중 하나는 정렬 과정에서 $O(n)$의 추가적인 메모리 공간을 사용한다는 점이었다. 그 대가로 빠른 속도와 안정성(Stable)을 얻었다.

 

그렇다면 힙 정렬은 어떨까? 힙 정렬의 가장 큰 실용적 장점은 바로 이 공간 복잡도에 있다.

공간 복잡도: 제자리에서 모든 것을 해결하다

힙 정렬은 주어진 배열을 힙 구조로 바꾼 뒤, 배열 내부에서 요소들의 위치를 교환하는 방식으로 동작한다. 즉, 정렬을 위한 별도의 큰 추가 배열이 필요 없다. 이러한 정렬을 '제자리 정렬(In-place Sort)'이라고 부르며, 힙 정렬의 공간 복잡도는 $O(1)$이다. 메모리 사용량이 극도로 제한된 환경에서는 병합 정렬보다 훨씬 매력적인 선택지가 될 수 있다.

시간 복잡도: 예측 가능한 성능

힙 정렬은 최선, 평균, 최악의 경우 모두 $O(n \log n)$의 시간 복잡도를 가진다. 이는 병합 정렬과 동일한 수준으로, 데이터의 초기 상태와 상관없이 항상 일정한 성능을 보장한다는 큰 장점이 있다.

• 힙 구성 단계: $O(n)$
• 정렬 단계: $n-1$개의 요소를 각각 힙에서 제거하고 재구성하는 과정($\log n$)을 반복하므로 $O(n \log n)$
• 총합: $O(n) + O(n \log n) = O(n \log n)$

그런데 "n개의 데이터를 힙에 넣는 과정이니, 삽입(O(log n))을 n번 반복해서 O(n log n)이 되어야 하는 것 아닌가?"

 

'힙 구성(Heapify) 단계가 왜 $O(n \log n)$이 아니고 $O(n)$이지?'라는 의문이 들 수 있다. 

 

만약 빈 힙에 원소를 하나씩 삽입한다면 $O(n \log n)$이 맞다. 하지만 일반적인 Heapify 과정은 이미 데이터가 있는 배열을 대상으로, 마지막 부모 노드부터 루트까지 거슬러 올라오며 힙 속성을 만족시키는 방식으로 동작한다.

 

힙의 전체 노드 중 거의 절반(리프 노드)은 아래로 내려갈 자식이 없어 연산이 필요 없고, 대부분의 노드가 트리의 아래쪽에 몰려있어 아래로 내려가는 연산(Down-Heap)을 하더라도 몇 번 수행하지 않는다. 모든 노드의 실제 연산 횟수를 수학적으로 계산해 보면 그 총합이 $O(n)$에 수렴한다. 따라서 이미 존재하는 배열을 힙으로 만드는 것은 우리가 생각하는 것보다 훨씬 효율적이다.

안정성(Stability): 힙 정렬의 결정적 약점

하지만 힙 정렬은 중요한 것을 하나 포기했다. 바로 안정성(Stability)이다. 힙을 구성하거나 재구성하는 과정에서 값의 교환이 일어나는데, 이때 값이 같은 요소들의 초기 순서가 뒤바뀔 수 있다. 따라서 힙 정렬은 '불안정 정렬(Unstable Sort)'에 속한다.

 

병합 정렬이 안정성을 보장했던 것과 비교하면 이는 분명한 단점이다. 다중 조건으로 정렬해야 하는 상황에서는 힙 정렬이 적합하지 않을 수 있다.

힙 정렬이 불안정한 이유: 값만 보고 교환하는 메커니즘

힙 정렬의 불안정성은 '대장'을 뽑아 맨 뒤로 보내는 정렬 단계에서 명확히 드러난다. 힙은 요소를 교환할 때 값의 크기만 고려할 뿐, 원래의 순서는 전혀 신경 쓰지 않기 때문이다.

간단한 예시를 통해 살펴보자.

 

같은 값 5를 가진 두 요소 5a와 5b가 있고, 초기 배열에서 5a가 5b보다 앞에 있었다고 가정해 보자.

1. 힙 구성 후: 여러 차례 교환을 거쳐 최대 힙이 구성된 결과, 우연히 5b가 루트에 위치하고 5a가 힙의 가장 마지막 요소가 되었다고 가정한다.
   • 현재 힙 배열: [5b, 4, 3, ..., 5a]

2. 첫 번째 정렬 단계 (Swap):
   • 규칙에 따라 루트(5b)와 가장 마지막 요소(5a)를 교환한다.
   • 교환 후 배열: [5a, 4, 3, ..., 5b]

3. 결과:
   • 5b는 이제 배열의 맨 뒤(arr[n-1])로 이동해 정렬이 완료된 것으로 처리된다.
   • 이후 남은 요소들을 정렬하고 나면 5a는 5b보다 앞선 위치에 놓이게 된다.
   • 최종적으로 정렬된 배열에서 두 요소의 순서는 [..., 5a, ..., 5b]가 되어, 초기 순서(5a가 먼저)와 뒤바뀌게 된다.

이처럼 힙 정렬은 알고리즘의 동작 방식상 같은 값을 가진 요소들의 상대적 순서를 보장하지 않으므로 '불안정 정렬'로 분류된다.

힙 정렬 vs 병합 정렬: 최종 비교

 

구분	힙 정렬 (Heap Sort)	병합 정렬 (Merge Sort)
시간 복잡도	O(nlogn)O(nlog⁡n)	O(nlogn)O(nlog⁡n)
공간 복잡도	O(1)O(1) (제자리 정렬)	O(n)O(n)
안정성	불안정 (Unstable)	안정 (Stable)

 

한편, 똑같은 $O(n \log n)$인데, 실제로는 퀵 정렬(Quick Sort) 같은 다른 정렬보다 힙 정렬이 느린 경향이 있다는 연구가 있다. 위키피디아의 힙 정렬(Heapsort) 항목에서는 이 현상의 핵심 원인을 다음과 같이 설명한다.

 

"The main advantage of quicksort is its much better locality of reference: partitioning is a linear scan with good spatial locality, and the recursive subdivision has good temporal locality."

— Wikipedia, "Heapsort"

(해석)
퀵 정렬의 주된 장점은 훨씬 더 나은 참조 지역성에 있다. 파티셔닝(분할)은 공간적 지역성이 좋은 선형 스캔이며, 재귀적 분할은 시간적 지역성이 좋다.

 

이론적인 시간 복잡도는 동일하지만, 실제 성능 테스트에서는 힙 정렬이 평균적으로 퀵 정렬보다 느린 경향을 보인는데, 가장 큰 이유는 참조 지역성(Locality of Reference), 즉 CPU 캐시 효율성 때문이라는 것이다.

 

힙 정렬은 힙을 재구성하는 과정에서 배열의 여기저기(예: 부모와 멀리 떨어진 자식)에 접근하며 데이터를 교환한다. 이런 비순차적인 메모리 접근은 CPU 캐시의 효율을 떨어뜨린다.

 

라마르카와 래드너의 ‘The Influence of Caches on the Performance of Sorting’ 논문에서도 힙 기반 HEx 알고리즘이 키 비교는 더 적게 하지만 참조 지역성이 낮아 캐시 미스가 많아지면서 CPU 시간이 3.88배 증가했다고 지적한다.

“the poor locality of reference generates numerous cache faults slowing down its performance. In fact, HEx uses 3.88 times more CPU time, even using 18.76% fewer key comparisons”

- The Influence of Caches on the Performance of Sorting
https://users.dcc.uchile.cl/~gnavarro/ps/algor09.pdf#:~:text=to%20pay%20a%20lower%20insertion,c

 

즉, 알고리즘의 이론적 연산 횟수(키 비교)가 아무리 적더라도, 메모리 접근 비효율로 인한 지연 시간(캐시 미스)이 그 이점을 모두 상쇄하고도 남아 전체 성능을 저하시킨다는 것을 의미한다.

 

반면 퀵 정렬이나 병합 정렬은 데이터를 순차적으로 접근하는 경향이 강해 캐시 효율성이 높고, 따라서 실제 실행 시간에서 더 좋은 성능을 보이는 경우가 많다. 알고리즘의 효율성을 시간 복잡도만으로 판단할 수 없는 재미있는 사례 중 하나이다.

 

 

결론적으로, 힙 정렬은 추가 메모리 없이 효율적인 정렬이 필요할 때 가장 먼저 고려할 수 있는 강력한 카드다. 반면, 데이터의 안정성이 중요하거나 메모리가 충분한 상황이라면 병합 정렬이 더 나은 선택일 수 있다.

 

---

🎬 Wrap up ! 

이번 글에서는 "가장 중요한 데이터를 어떻게 가장 빠르게 찾을까?"라는 실용적인 질문에서 출발했다. 그 답을 찾기 위해 '힙' 자료구조의 규칙들을 알아보았고, 이 특성을 이용해 '힙 정렬'이 탄생하는 과정도 따라가 보았다.

 

여기서 그치지 않고 제자리 정렬이라는 장점과 불안정성이라는 약점, 그리고 CPU 캐시 효율에 따라 실제 성능이 달라지는 현실적인 이야기까지 짚어보았다. 

 

그렇다면 이 똑똑한 힙(Heap)은 어디에 쓰일까? 당장 운영체제가 여러 프로세스 중 '누구 먼저?'를 결정할 때, 혹은 최단 경로를 찾는 알고리즘에서 가장 '가까운' 길을 고를 때 우선순위 큐의 형태로 활약한다. 힙 정렬 자체도 메모리 사용이 지극히 제한적인 임베디드 시스템 같은 환경에서 제 역할을 톡톡히 해낸다.

 

이번 글에서는 '힙'이라는 자료구조를 통해 힙 정렬의 원리와 특징을 간략히 알아보았지만, 이와 관련해 우리가 더 탐구해 볼 수 있는 주제들은 훨씬 많다!

 

힙의 기본 연산을 Java 코드로 직접 구현하고 PriorityQueue 클래스를 만들어보는 실용적인 주제부터 시작해, 이진 힙을 넘어 k개의 자식을 갖는 d-ary 힙의 성능을 분석하거나 퀵 정렬의 약점을 보완하는 인트로 정렬(Introsort)의 핵심 부품으로 활약하는 모습도 살펴볼 수 있겠다.

 

더 나아가 피보나치 힙(Fibonacci Heap) 같은 고급 구조나 힙의 캐시 문제를 다루는 캐시 부주의 알고리즘에 대한 논의에 이르기까지, 파고들수록 흥미로운 이야기들이 여전히 많다.