힙정렬 시각화
이진 힙 트리와 배열을 동시에 보며 힙정렬 과정을 학습합니다
정렬★★☆
속도
1 / 1비교 횟수: 0스왑 횟수: 0힙 크기: 15
배열 크기15
비교 중스왑정렬 완료힙 내부힙 외부
이진 힙이 구성되고 최댓값이 추출되는 과정을 관찰하세요.
힙정렬이란?
힙정렬(Heap Sort)은 이진 힙 자료구조를 활용한 비교 기반 정렬 알고리즘입니다. 먼저 최대 힙을 구성한 후, 루트(최댓값)를 반복적으로 추출하여 정렬합니다. 항상 O(n log n)을 보장하며 추가 메모리가 필요 없는 제자리 정렬입니다.
사용 방법
- 1배열 크기를 조절하세요 (트리 시각화를 위해 최대 31 권장)
- 2상단 트리와 하단 막대 차트가 동시에 업데이트됩니다
- 3힙 구성 단계에서 아래→위로 힙 속성이 복원되는 것을 관찰하세요
- 4추출 단계에서 루트(최댓값)가 배열 끝으로 이동합니다
- 5회색 노드는 이미 정렬되어 힙에서 제외된 요소입니다
동작 원리
- 1입력 배열을 최대 힙(Max-Heap)으로 변환합니다 (Build Heap, O(n))
- 2힙의 루트(최댓값)와 마지막 요소를 교환합니다
- 3힙 크기를 1 줄이고 루트에서 Heapify(하향식 조정)를 수행합니다
- 4루트에서부터 자식과 비교하며 큰 값과 교환을 반복합니다
- 5힙 크기가 1이 될 때까지 반복하면 오름차순 정렬이 완료됩니다
실무 활용
- •운영체제의 우선순위 큐 구현(프로세스 스케줄링)에 활용됩니다
- •실시간 시스템에서 최악 O(n log n) 보장이 필요한 경우에 사용됩니다
- •Top-K 문제 — 대용량 데이터에서 상위 K개 추출(뉴스 피드 순위, 검색 결과 상위 N개)에 사용됩니다
- •이벤트 기반 시뮬레이션의 타이머 관리에 활용됩니다
- •다익스트라/A* 알고리즘의 우선순위 큐 기반으로 사용됩니다
비슷한 알고리즘
- •퀵정렬 — 평균 더 빠르지만 최악 O(n²). 힙정렬은 항상 O(n log n)이나 캐시 효율이 낮아 실측은 느림
- •병합정렬 — 역시 O(n log n) 보장. 힙정렬은 추가 메모리 불필요(제자리)이나 불안정 정렬
- •이진 힙 vs 피보나치 힙 — 피보나치 힙은 decrease-key가 O(1) 분할상환이라 다익스트라에 이론적으로 더 빠름
학습 팁
- •최대 힙에서 부모는 항상 자식보다 크거나 같습니다
- •힙 구성은 O(n)에 완료됩니다 (O(n log n)이 아님!)
- •추출 단계에서 매번 최댓값이 올바른 위치로 이동합니다
- •역순 배열에서 힙 구성이 가장 적은 스왑으로 완료됩니다 (이미 힙 조건 충족)
자주 묻는 질문
Q. 퀵정렬과 비교하면?
A. 힙정렬은 최악 O(n log n)을 보장하지만, 캐시 지역성이 나빠 실제로는 퀵정렬보다 느립니다. 최악 케이스 보장이 중요할 때 사용합니다.
Q. 안정 정렬인가요?
A. 아닙니다. 힙에서 추출할 때 같은 값의 상대적 순서가 바뀔 수 있습니다.
Q. 우선순위 큐와의 관계는?
A. 힙은 우선순위 큐의 대표적인 구현 방식입니다. 다익스트라, A* 등에서 사용하는 우선순위 큐가 바로 이진 힙입니다.