이미지 로딩 중...
AI Generated
2025. 11. 8. · 3 Views
Heapify 배열을 힙으로 변환하는 완벽 가이드
배열을 효율적으로 힙 자료구조로 변환하는 Heapify 알고리즘을 깊이 있게 다룹니다. 시간복잡도 O(n)으로 작동하는 원리와 실무 활용법을 상세한 코드 예제와 함께 설명합니다.
목차
- Heapify의 핵심 개념 - 배열을 힙으로 효율적으로 변환하기
- Sift-down 연산 - 힙 속성 유지의 핵심
- Sift-up 연산 - 새 요소 삽입의 핵심
- 힙에서 최댓값 추출하기 - Extract Max 연산
- 힙 정렬 - Heapify와 Extract Max의 응용
- k번째 최댓값 찾기 - Heapify의 실용적 응용
- 힙의 시간복잡도 분석 - 왜 Heapify는 O(n)인가
- 우선순위 큐 구현 - 힙의 대표적 응용
1. Heapify의 핵심 개념 - 배열을 힙으로 효율적으로 변환하기
시작하며
여러분이 우선순위 큐를 구현하거나 대용량 데이터에서 최댓값/최솟값을 반복적으로 추출해야 하는 상황을 겪어본 적 있나요? 단순히 배열을 정렬하면 O(n log n)이 걸리고, 매번 선형 탐색을 하면 O(n)씩 소요되어 비효율적입니다.
이런 문제는 실시간 시스템이나 스케줄링 알고리즘, 다익스트라 최단 경로 알고리즘 등 실제 개발 현장에서 자주 발생합니다. 특히 데이터가 계속 추가되고 최댓값이나 최솟값을 빠르게 찾아야 할 때, 일반적인 배열로는 성능 문제가 발생합니다.
바로 이럴 때 필요한 것이 Heapify입니다. Heapify를 사용하면 단 O(n) 시간에 배열을 힙 자료구조로 변환하여, 이후 O(log n) 시간에 최댓값/최솟값 추출과 삽입이 가능해집니다.
개요
간단히 말해서, Heapify는 정렬되지 않은 배열을 힙 속성을 만족하는 자료구조로 변환하는 알고리즘입니다. 힙은 완전 이진 트리 구조로, 부모 노드가 항상 자식 노드보다 크거나(Max Heap) 작은(Min Heap) 속성을 가집니다.
실무에서는 우선순위 큐 구현, 힙 정렬, k번째 최댓값 찾기, 실시간 중앙값 계산 등에 사용됩니다. 예를 들어, CPU 작업 스케줄링에서 우선순위가 높은 프로세스를 빠르게 선택하거나, 네트워크 패킷 처리에서 긴급 패킷을 먼저 처리할 때 매우 유용합니다.
기존에는 배열에 요소를 하나씩 삽입하면서 힙을 구성했다면(O(n log n)), 이제는 Bottom-up 방식의 Heapify를 사용하여 O(n) 시간에 변환할 수 있습니다. Heapify의 핵심 특징은 다음과 같습니다: (1) 배열의 마지막 부모 노드부터 역순으로 처리하여 효율성을 높입니다.
(2) 각 노드에서 Sift-down 연산을 수행하여 힙 속성을 만족시킵니다. (3) 완전 이진 트리의 속성을 이용해 배열 인덱스로 부모-자식 관계를 O(1)에 계산합니다.
이러한 특징들이 알고리즘의 시간복잡도를 획기적으로 줄여주는 핵심 요소입니다.
코드 예제
// Max Heap을 구성하는 Heapify 구현
function heapify(arr) {
const n = arr.length;
// 마지막 부모 노드부터 역순으로 sift-down
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
siftDown(arr, n, i);
}
return arr;
}
function siftDown(arr, n, i) {
let largest = i; // 현재 노드를 largest로 초기화
const left = 2 * i + 1; // 왼쪽 자식 인덱스
const right = 2 * i + 2; // 오른쪽 자식 인덱스
// 왼쪽 자식이 더 크면 largest 갱신
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 오른쪽 자식이 더 크면 largest 갱신
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// largest가 바뀌었으면 swap하고 재귀적으로 sift-down
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
siftDown(arr, n, largest);
}
}
// 사용 예시
const arr = [3, 9, 2, 1, 4, 5];
heapify(arr);
console.log(arr); // [9, 4, 5, 1, 3, 2] - Max Heap
설명
이것이 하는 일: Heapify는 정렬되지 않은 배열을 입력받아, 부모 노드가 항상 자식 노드보다 큰(또는 작은) 힙 속성을 만족하도록 재배치합니다. 핵심은 배열을 완전 이진 트리로 간주하고, Bottom-up 방식으로 각 서브트리가 힙 속성을 만족하도록 만드는 것입니다.
첫 번째 단계에서는 배열의 마지막 부모 노드를 찾습니다. 완전 이진 트리에서 인덱스 i의 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2이므로, 마지막 부모 노드는 Math.floor(n/2)-1입니다.
이 지점부터 역순으로 처리하는 이유는, 리프 노드(자식이 없는 노드)는 이미 힙 속성을 만족하므로 처리할 필요가 없기 때문입니다. 이렇게 하면 불필요한 연산을 절반으로 줄일 수 있습니다.
두 번째 단계에서는 각 노드에 대해 sift-down 연산을 수행합니다. sift-down은 현재 노드와 자식 노드들을 비교하여, 자식 중 더 큰 값과 위치를 교환하는 과정입니다.
현재 노드가 두 자식보다 모두 크면 힙 속성을 만족하므로 종료하고, 그렇지 않으면 더 큰 자식과 교환한 후 교환된 위치에서 재귀적으로 sift-down을 계속합니다. 이 과정은 리프 노드에 도달하거나 힙 속성을 만족할 때까지 반복됩니다.
세 번째 단계와 최종 결과: 모든 부모 노드에 대해 sift-down을 완료하면, 전체 배열이 힙 속성을 만족하게 됩니다. 루트 노드(인덱스 0)에는 최댓값이 위치하고, 모든 부모는 자식보다 큰 값을 가집니다.
중요한 점은 이 알고리즘의 시간복잡도가 O(n)이라는 것입니다. 직관적으로는 n개 노드에 대해 각각 O(log n) 연산을 하므로 O(n log n)처럼 보이지만, 실제로는 하위 레벨의 노드들은 sift-down 거리가 짧아서 평균적으로 O(n)이 됩니다.
여러분이 이 코드를 사용하면 대용량 데이터에서 최댓값을 반복적으로 추출하는 작업을 효율적으로 처리할 수 있습니다. 초기 힙 구성에 O(n), 각 추출에 O(log n)이 소요되므로, k번 추출해도 O(n + k log n)으로 일반 정렬의 O(n log n)보다 빠릅니다.
또한 동적으로 데이터가 추가되는 상황에서도 O(log n)에 삽입이 가능하여, 실시간 시스템에 매우 적합합니다.
실전 팁
💡 배열 인덱스로 부모-자식 관계를 계산할 때, 인덱스 i의 부모는 Math.floor((i-1)/2), 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2임을 기억하세요. 이 공식을 외워두면 트리 구조 없이도 배열만으로 힙을 효율적으로 구현할 수 있습니다.
💡 Heapify를 처음부터(인덱스 0부터) 순회하지 마세요. 이는 O(n log n)이 걸립니다. 반드시 마지막 부모 노드부터 역순으로 처리해야 O(n)의 효율을 얻을 수 있습니다. 많은 초보자들이 이 부분을 놓쳐서 성능 손실을 겪습니다.
💡 실무에서는 JavaScript의 경우 배열 내장 메서드를 활용하되, 힙 연산 시에는 splice나 unshift 같은 O(n) 연산을 피하고 인덱스 기반 접근만 사용하세요. 성능이 중요한 경우 TypedArray를 고려해보는 것도 좋습니다.
💡 디버깅 시 힙이 제대로 구성되었는지 확인하려면, 모든 부모 노드에 대해 arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 조건을 검증하는 함수를 작성하세요. 단위 테스트에 이를 포함하면 버그를 조기에 발견할 수 있습니다.
💡 Min Heap이 필요한 경우 비교 연산자만 반대로 바꾸면 됩니다(arr[left] < arr[largest] 등). 또는 Comparator 함수를 파라미터로 받아 범용적으로 사용할 수 있게 만들면, 객체 배열이나 커스텀 정렬 기준에도 적용 가능합니다.
2. Sift-down 연산 - 힙 속성 유지의 핵심
시작하며
여러분이 힙에서 루트 노드를 제거하거나, 특정 노드의 값을 감소시켰을 때 힙 속성이 깨지는 상황을 마주한 적 있나요? 이럴 때 전체 힙을 다시 구성하면 O(n log n)의 시간이 소요되어 비효율적입니다.
이런 문제는 우선순위 큐에서 최댓값을 추출한 후, 또는 힙 정렬 과정에서 반복적으로 발생합니다. 힙의 장점은 O(log n)의 빠른 연산인데, 매번 전체를 재구성하면 이 장점이 사라집니다.
바로 이럴 때 필요한 것이 Sift-down 연산입니다. Sift-down은 힙 속성이 깨진 노드를 적절한 위치로 내려보내면서, O(log n) 시간에 힙을 복구합니다.
개요
간단히 말해서, Sift-down은 특정 노드가 자식보다 작을 때(Max Heap 기준), 그 노드를 자식과 교환하면서 아래로 내려보내는 연산입니다. 이 연산은 힙의 핵심 동작으로, Heapify 구성뿐만 아니라 힙에서 요소 제거, 힙 정렬, 우선순위 감소 등 거의 모든 힙 연산에 사용됩니다.
실무에서는 우선순위 큐의 dequeue 연산, 힙 정렬의 각 단계, 다익스트라 알고리즘의 거리 갱신 등에서 필수적으로 활용됩니다. 예를 들어, 운영체제의 프로세스 스케줄러에서 가장 높은 우선순위 프로세스를 실행한 후, 다음 프로세스를 선택할 때 sift-down이 사용됩니다.
기존에는 힙에서 요소를 제거한 후 전체를 재구성했다면, 이제는 sift-down 하나로 O(log n)에 힙을 복구할 수 있습니다. Sift-down의 핵심 특징은: (1) 현재 노드와 두 자식 중 더 큰 자식을 비교하여 교환합니다.
(2) 교환 후 새로운 위치에서 재귀적으로 또는 반복적으로 계속 진행합니다. (3) 리프 노드에 도달하거나 힙 속성을 만족하면 종료합니다.
이러한 특징들이 힙의 높이(log n)만큼만 연산을 수행하게 하여 효율성을 보장합니다.
코드 예제
// 재귀 방식의 Sift-down (Max Heap)
function siftDownRecursive(arr, n, i) {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
// 왼쪽 자식과 비교
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 오른쪽 자식과 비교
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 교환이 필요하면 swap하고 재귀 호출
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
siftDownRecursive(arr, n, largest);
}
}
// 반복 방식의 Sift-down (스택 오버플로우 방지)
function siftDownIterative(arr, n, i) {
while (true) {
let largest = i;
const left = 2 * i + 1;
const 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;
[arr[i], arr[largest]] = [arr[largest], arr[i]];
i = largest; // 다음 위치로 이동
}
}
설명
이것이 하는 일: Sift-down은 힙 속성이 깨진 특정 노드를 올바른 위치로 이동시켜 힙을 복구합니다. 핵심 아이디어는 현재 노드가 두 자식보다 작으면, 더 큰 자식과 위치를 바꾸고, 이 과정을 힙 속성을 만족할 때까지 반복하는 것입니다.
첫 번째 단계에서는 현재 노드 i의 두 자식 인덱스를 계산합니다: left = 2i+1, right = 2i+2. 그런 다음 세 노드(현재, 왼쪽 자식, 오른쪽 자식) 중에서 가장 큰 값을 찾습니다.
이때 자식 인덱스가 배열 범위를 벗어나는지 반드시 확인해야 합니다(left < n, right < n). 이 검사를 빠뜨리면 런타임 에러가 발생할 수 있습니다.
두 번째 단계에서는 가장 큰 값이 현재 노드가 아니라면, 즉 자식 중 하나가 더 크다면, 그 자식과 현재 노드를 교환합니다. 중요한 점은 두 자식 중 더 큰 자식과 교환해야 한다는 것입니다.
만약 더 작은 자식과 교환하면, 교환 후에도 힙 속성이 깨질 수 있습니다. 예를 들어, 부모가 5, 왼쪽 자식이 10, 오른쪽 자식이 8일 때, 5를 8과 교환하면 부모 8 < 자식 10이 되어 여전히 힙 속성 위반입니다.
세 번째 단계와 최종 결과: 교환 후 새로운 위치(교환된 자식의 위치)에서 다시 sift-down을 수행합니다. 재귀 방식에서는 함수를 다시 호출하고, 반복 방식에서는 인덱스 i를 업데이트하여 while 루프를 계속합니다.
이 과정은 두 가지 조건 중 하나를 만족할 때 종료됩니다: (1) 현재 노드가 두 자식보다 모두 큰 경우(힙 속성 만족), (2) 리프 노드에 도달한 경우(더 이상 자식이 없음). 최악의 경우 트리의 높이만큼 내려가므로 시간복잡도는 O(log n)입니다.
여러분이 이 연산을 사용하면 힙에서 최댓값을 제거할 때 매우 효율적입니다. 일반적인 패턴은: (1) 루트(최댓값)를 제거, (2) 마지막 요소를 루트로 이동, (3) 루트에서 sift-down 수행입니다.
이렇게 하면 O(log n)에 제거가 완료되고, 다음 최댓값이 자동으로 루트에 위치합니다. 또한 힙 정렬에서는 이 과정을 n번 반복하여 O(n log n)에 정렬을 완성합니다.
실전 팁
💡 재귀 방식은 코드가 간결하지만 깊은 힙에서는 스택 오버플로우 위험이 있습니다. 실무에서는 반복 방식을 선호하며, 특히 임베디드 시스템이나 스택 크기가 제한된 환경에서는 필수적으로 반복 방식을 사용하세요.
💡 두 자식 중 더 큰 자식과 교환하는 것을 잊지 마세요. 이는 매우 흔한 실수로, 더 작은 자식과 교환하면 교환 후에도 힙 속성이 깨질 수 있습니다. 코드 리뷰 시 이 부분을 특히 주의깊게 확인하세요.
💡 성능 최적화를 위해 swap 횟수를 줄일 수 있습니다. 매번 교환하지 말고, 최종 위치를 먼저 찾은 후 한 번만 이동하는 방식을 사용하면 캐시 효율성이 향상됩니다. 이는 힙 정렬 구현 시 특히 유용합니다.
💡 Min Heap에서는 비교 조건만 반대로 하면 됩니다(arr[left] < arr[smallest]). 범용적인 구현을 위해 comparator 함수를 파라미터로 받아 비교 로직을 외부에서 주입할 수 있게 만드세요.
💡 디버깅 시 각 sift-down 단계마다 힙을 시각화하거나 로그를 출력하면 도움이 됩니다. 특히 교환이 일어나는 인덱스와 값을 추적하면, 알고리즘의 동작을 이해하고 버그를 빠르게 찾을 수 있습니다.
3. Sift-up 연산 - 새 요소 삽입의 핵심
시작하며
여러분이 힙에 새로운 요소를 삽입할 때, 단순히 배열 끝에 추가하면 힙 속성이 깨지는 문제를 겪어본 적 있나요? 이럴 때 전체 heapify를 다시 수행하면 O(n)이 걸려서 비효율적입니다.
이런 문제는 동적으로 데이터가 계속 추가되는 실시간 시스템에서 치명적입니다. 예를 들어, 실시간 로그 분석 시스템에서 우선순위가 높은 이벤트를 계속 추가하면서 최우선 이벤트를 빠르게 처리해야 하는 경우, 매번 O(n) 연산은 허용되지 않습니다.
바로 이럴 때 필요한 것이 Sift-up 연산입니다. Sift-up은 새로 추가된 요소를 적절한 위치로 위로 올리면서, O(log n) 시간에 힙 속성을 복구합니다.
개요
간단히 말해서, Sift-up은 새로 추가된 요소가 부모보다 클 때(Max Heap 기준), 그 요소를 부모와 교환하면서 위로 올려보내는 연산입니다. 이 연산은 힙에 요소를 삽입할 때 필수적으로 사용되며, 힙 속성을 유지하면서도 O(log n)의 효율성을 보장합니다.
실무에서는 우선순위 큐의 enqueue 연산, 다익스트라 알고리즘에서 더 짧은 경로를 발견했을 때 우선순위 갱신, 이벤트 기반 시뮬레이션에서 새 이벤트 추가 등에 활용됩니다. 예를 들어, 웹 서버의 요청 처리 큐에서 VIP 사용자의 요청이 들어오면 높은 우선순위로 삽입하고 sift-up으로 적절한 위치에 배치합니다.
기존에는 요소를 추가한 후 전체 배열을 다시 heapify 했다면, 이제는 sift-up 하나로 O(log n)에 삽입이 완료됩니다. Sift-up의 핵심 특징은: (1) 배열의 끝에 새 요소를 추가한 후 시작합니다.
(2) 현재 노드를 부모와 비교하여, 부모보다 크면 교환합니다. (3) 루트에 도달하거나 힙 속성을 만족할 때까지 반복합니다.
이러한 특징들이 삽입 연산을 O(log n)으로 유지하게 해주며, 힙을 동적 자료구조로 효과적으로 활용할 수 있게 합니다.
코드 예제
// Sift-up 연산 구현 (Max Heap)
function siftUp(arr, i) {
// 부모 인덱스 계산
let parent = Math.floor((i - 1) / 2);
// 루트에 도달하지 않았고, 현재 값이 부모보다 크면
while (i > 0 && arr[i] > arr[parent]) {
// 부모와 교환
[arr[i], arr[parent]] = [arr[parent], arr[i]];
// 인덱스를 부모 위치로 이동
i = parent;
parent = Math.floor((i - 1) / 2);
}
}
// 힙에 요소 삽입하는 함수
function heapInsert(arr, value) {
// 배열 끝에 새 요소 추가
arr.push(value);
// 마지막 인덱스에서 sift-up 수행
siftUp(arr, arr.length - 1);
return arr;
}
// 사용 예시
const heap = [9, 4, 5, 1, 3, 2];
heapInsert(heap, 10);
console.log(heap); // [10, 4, 9, 1, 3, 2, 5] - 10이 루트로 올라감
heapInsert(heap, 6);
console.log(heap); // [10, 6, 9, 4, 3, 2, 5, 1] - 6이 적절한 위치에 삽입
설명
이것이 하는 일: Sift-up은 배열 끝에 추가된 새 요소를 올바른 위치로 이동시켜 힙 속성을 유지합니다. 핵심은 새 요소가 부모보다 크면 계속 위로 올라가고, 부모보다 작거나 같으면 멈추는 것입니다.
첫 번째 단계에서는 새 요소를 배열의 끝에 추가합니다(arr.push(value)). 이는 완전 이진 트리의 속성을 유지하기 위함입니다.
힙은 항상 완전 이진 트리여야 하므로, 새 노드는 항상 가장 아래 레벨의 가장 왼쪽 빈 자리에 추가되어야 합니다. 배열 표현에서 이는 배열의 끝에 해당합니다.
그 후 이 위치에서 sift-up을 시작합니다. 두 번째 단계에서는 현재 노드의 부모를 계산하고 비교합니다.
인덱스 i의 부모는 Math.floor((i-1)/2)입니다. 현재 노드가 부모보다 크면 두 요소를 교환합니다.
이때 중요한 것은 형제 노드(부모의 다른 자식)와는 비교할 필요가 없다는 점입니다. 부모보다 큰 것만 확인하면, 교환 후에도 형제와의 관계는 자동으로 힙 속성을 만족합니다.
왜냐하면 Max Heap에서 부모는 모든 자식보다 크거나 같아야 하므로, 현재 노드가 새 부모가 되면 자동으로 이전 형제보다 크거나 같게 됩니다. 세 번째 단계와 최종 결과: 교환 후 인덱스를 부모의 위치로 업데이트하고, 다시 새로운 부모를 계산하여 과정을 반복합니다.
이는 두 가지 조건 중 하나를 만족할 때 종료됩니다: (1) 루트에 도달한 경우(i === 0), (2) 현재 노드가 부모보다 작거나 같은 경우(힙 속성 만족). 최악의 경우 루트까지 올라가므로 시간복잡도는 O(log n)입니다.
평균적으로는 트리의 중간쯤에서 멈추므로 실제로는 더 빠릅니다. 여러분이 이 연산을 사용하면 힙을 동적 자료구조로 활용할 수 있습니다.
초기 배열을 O(n)에 heapify한 후, 이후 삽입은 각각 O(log n)에 수행되므로, n개 요소를 하나씩 삽입해도 총 O(n log n)입니다. 이는 초기 heapify O(n)보다는 느리지만, 데이터가 동적으로 들어오는 상황에서는 피할 수 없습니다.
중요한 것은 각 삽입이 일정하게 O(log n)을 보장하여 실시간 시스템에서 예측 가능한 성능을 제공한다는 점입니다.
실전 팁
💡 부모 인덱스 계산 시 Math.floor((i-1)/2)를 사용하세요. (i-1)/2만 사용하면 소수점이 나와서 배열 인덱싱 오류가 발생할 수 있습니다. 또한 i가 0일 때는 루프가 실행되지 않도록 i > 0 조건을 반드시 포함하세요.
💡 Sift-up은 반복 방식이 더 효율적입니다. Sift-down과 달리 sift-up은 항상 한 방향(위)으로만 진행하므로 재귀 호출의 오버헤드가 불필요합니다. 실무에서는 항상 반복 방식을 사용하세요.
💡 성능 최적화를 위해 교환 횟수를 줄일 수 있습니다. 매번 swap하지 말고, 삽입할 값을 변수에 저장해두고 부모들만 아래로 이동시킨 후, 최종 위치에 한 번만 값을 쓰는 방식을 사용하면 메모리 쓰기 연산이 줄어듭니다.
💡 우선순위 큐를 구현할 때는 insert와 extractMax(또는 extractMin)를 쌍으로 제공하세요. Insert는 sift-up, extractMax는 sift-down을 사용합니다. 이 두 연산만으로도 완전한 우선순위 큐를 구현할 수 있습니다.
💡 Min Heap 변환 시에는 arr[i] > arr[parent]를 arr[i] < arr[parent]로 바꾸기만 하면 됩니다. 또는 값을 삽입할 때 음수로 변환하여 Max Heap에 넣으면 Min Heap처럼 동작하게 할 수도 있습니다(우선순위가 숫자인 경우).
4. 힙에서 최댓값 추출하기 - Extract Max 연산
시작하며
여러분이 우선순위 큐에서 가장 우선순위가 높은 작업을 처리하고 제거해야 하는 상황을 겪어본 적 있나요? 단순히 배열에서 최댓값을 찾아 제거하면 O(n)이 걸리고, 삭제 후 빈 공간을 채우는 것도 복잡합니다.
이런 문제는 작업 스케줄링, 이벤트 처리, 다익스트라 최단 경로 알고리즘 등 실제 개발 현장에서 핵심적인 연산입니다. 효율적인 추출이 없으면 전체 시스템의 성능이 저하됩니다.
바로 이럴 때 필요한 것이 Extract Max 연산입니다. 힙에서는 루트가 항상 최댓값이므로 O(1)에 찾고, sift-down으로 O(log n)에 제거와 재구성을 완료할 수 있습니다.
개요
간단히 말해서, Extract Max는 힙의 루트(최댓값)를 제거하고, 마지막 요소를 루트로 옮긴 후 sift-down으로 힙을 복구하는 연산입니다. 이 연산은 우선순위 큐의 핵심 기능으로, dequeue 또는 poll 연산에 해당합니다.
실무에서는 CPU 스케줄러가 다음 실행할 프로세스를 선택할 때, 네트워크 라우터가 다음 전송할 패킷을 선택할 때, 다익스트라 알고리즘이 다음 방문할 노드를 선택할 때 사용됩니다. 예를 들어, 게임 서버의 이벤트 루프에서 다음에 처리할 이벤트를 선택하거나, 실시간 분석 시스템에서 가장 중요한 알림을 먼저 전송할 때 필수적입니다.
기존에는 최댓값을 찾아 제거한 후 배열을 재정렬했다면, 이제는 Extract Max 하나로 O(log n)에 제거와 힙 복구가 동시에 완료됩니다. Extract Max의 핵심 특징은: (1) 루트를 제거하고 마지막 요소를 루트로 이동시킵니다.
(2) 루트에서 sift-down을 수행하여 힙 속성을 복구합니다. (3) 배열 크기를 줄여 완전 이진 트리 구조를 유지합니다.
이러한 특징들이 제거 연산을 O(log n)으로 유지하며, 힙의 모든 장점을 살려줍니다.
코드 예제
// Max Heap에서 최댓값 추출
function extractMax(arr) {
// 빈 힙 체크
if (arr.length === 0) {
throw new Error('Heap is empty');
}
// 힙에 요소가 하나만 있으면 바로 반환
if (arr.length === 1) {
return arr.pop();
}
// 루트(최댓값)를 저장
const max = arr[0];
// 마지막 요소를 루트로 이동
arr[0] = arr.pop();
// 루트에서 sift-down 수행하여 힙 복구
siftDown(arr, arr.length, 0);
return max;
}
// Sift-down 헬퍼 함수
function siftDown(arr, n, i) {
while (true) {
let largest = i;
const left = 2 * i + 1;
const 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;
[arr[i], arr[largest]] = [arr[largest], arr[i]];
i = largest;
}
}
// 사용 예시
const heap = [10, 6, 9, 4, 3, 2, 5, 1];
console.log(extractMax(heap)); // 10
console.log(heap); // [9, 6, 5, 4, 3, 2, 1] - 힙 속성 유지
console.log(extractMax(heap)); // 9
console.log(heap); // [6, 4, 5, 1, 3, 2]
설명
이것이 하는 일: Extract Max는 힙의 가장 큰 값인 루트를 제거하고 반환하면서, 동시에 힙 속성을 유지합니다. 핵심은 루트를 제거한 빈 자리를 마지막 요소로 채우고, sift-down으로 올바른 위치로 내려보내는 것입니다.
첫 번째 단계에서는 예외 처리와 특수 케이스를 확인합니다. 빈 힙에서 추출하려고 하면 에러를 던져야 합니다.
이는 매우 중요한데, 빈 배열에 접근하면 undefined가 반환되어 나중에 디버깅하기 어려운 버그가 발생할 수 있습니다. 또한 요소가 하나만 있는 경우는 단순히 pop()으로 제거하고 반환하면 됩니다.
이 경우 sift-down이 불필요하며, 불필요한 연산을 피하면 성능이 향상됩니다. 두 번째 단계에서는 루트 값(최댓값)을 임시 변수에 저장합니다(const max = arr[0]).
그 후 배열의 마지막 요소를 pop()으로 제거하여 루트 위치에 넣습니다(arr[0] = arr.pop()). 이 방법이 중요한 이유는: (1) pop()은 O(1) 연산입니다.
(2) 마지막 요소를 루트로 이동하면 완전 이진 트리 구조가 유지됩니다. 만약 다른 위치의 요소를 제거하면 트리에 빈 공간이 생겨 완전 이진 트리가 아니게 됩니다.
세 번째 단계와 최종 결과: 루트 위치(인덱스 0)에서 sift-down을 수행합니다. 이전에 마지막 요소였던 값이 루트에 있으므로, 대부분의 경우 힙 속성을 위반합니다.
Sift-down은 이 값을 적절한 위치로 내려보내면서 힙 속성을 복구합니다. 최악의 경우 리프까지 내려가므로 O(log n)이 소요됩니다.
최종적으로 저장해둔 max 값을 반환하면, 호출자는 최댓값을 받고 힙은 여전히 힙 속성을 만족하는 상태로 남습니다. 여러분이 이 연산을 사용하면 반복적으로 최댓값을 추출하는 작업을 효율적으로 처리할 수 있습니다.
예를 들어, k개의 최댓값을 추출하려면 extractMax를 k번 호출하면 되며, 총 시간복잡도는 O(k log n)입니다. 이는 전체 정렬 O(n log n)보다 k가 작을 때 훨씬 효율적입니다.
또한 힙 정렬을 구현할 때는 heapify 후 extractMax를 n번 반복하여 O(n log n)에 정렬을 완성할 수 있습니다.
실전 팁
💡 빈 힙 체크는 필수입니다. 프로덕션 코드에서는 에러를 던지거나, null을 반환하거나, Option 타입을 사용하여 빈 경우를 명확히 처리하세요. 런타임 에러를 방지하고 코드의 견고성을 높입니다.
💡 마지막 요소를 루트로 이동할 때 arr[0] = arr.pop()을 한 줄로 처리하면 효율적입니다. arr.pop()은 마지막 요소를 제거하고 반환하므로, 별도로 arr[arr.length-1]에 접근할 필요가 없습니다.
💡 반복적으로 extractMax를 호출하는 경우, 추출된 값들을 배열 끝에 쌓으면 힙 정렬이 됩니다. 이때 같은 배열을 재사용하여 추가 메모리 없이 in-place 정렬이 가능합니다(공간복잡도 O(1)).
💡 우선순위 큐를 구현할 때는 extractMax와 heapInsert를 함께 제공하세요. 이 두 연산만으로 완전한 우선순위 큐가 됩니다. 추가로 peek(최댓값 확인만 하고 제거하지 않음)도 제공하면 유용합니다: peek()는 단순히 arr[0]을 반환하면 되므로 O(1)입니다.
💡 Min Heap에서 extractMin을 구현할 때는 동일한 로직에 sift-down만 Min Heap 버전을 사용하면 됩니다. 함수 이름과 주석을 적절히 변경하여 혼동을 방지하세요.
5. 힙 정렬 - Heapify와 Extract Max의 응용
시작하며
여러분이 대용량 데이터를 정렬해야 하는데, 추가 메모리를 거의 사용하지 않으면서도 O(n log n)을 보장하는 알고리즘이 필요했던 적 있나요? 퀵 정렬은 평균 O(n log n)이지만 최악의 경우 O(n²)이고, 병합 정렬은 O(n) 추가 메모리가 필요합니다.
이런 문제는 메모리가 제한된 임베디드 시스템이나, 최악의 경우에도 성능을 보장해야 하는 실시간 시스템에서 중요합니다. 예를 들어, 항공기 제어 시스템이나 의료 기기에서는 최악의 경우 성능이 보장되어야 합니다.
바로 이럴 때 필요한 것이 힙 정렬입니다. 힙 정렬은 heapify와 반복적인 extractMax를 사용하여, 추가 메모리 O(1)로 최악의 경우에도 O(n log n)을 보장합니다.
개요
간단히 말해서, 힙 정렬은 배열을 힙으로 변환한 후, 반복적으로 최댓값을 추출하여 배열 끝부터 채워나가는 정렬 알고리즘입니다. 힙 정렬의 가장 큰 장점은 in-place 정렬이 가능하고(O(1) 추가 메모리), 최악의 경우에도 O(n log n)을 보장한다는 것입니다.
실무에서는 메모리가 제한된 환경, 최악의 경우 성능이 중요한 시스템, 외부 정렬(대용량 파일 정렬)의 내부 정렬 알고리즘으로 사용됩니다. 예를 들어, 데이터베이스의 ORDER BY 절 구현, 운영체제의 페이지 교체 알고리즘, 대용량 로그 파일 정렬 등에 활용됩니다.
기존 정렬 알고리즘과 비교하면: 퀵 정렬은 평균적으로 더 빠르지만 최악의 경우 O(n²), 병합 정렬은 안정적이지만 O(n) 추가 메모리 필요, 힙 정렬은 항상 O(n log n)이며 O(1) 추가 메모리만 사용합니다. 힙 정렬의 핵심 특징은: (1) 먼저 배열을 Max Heap으로 변환합니다(O(n)).
(2) 반복적으로 루트(최댓값)를 마지막 위치와 교환하고 힙 크기를 줄입니다. (3) 각 교환 후 루트에서 sift-down을 수행하여 힙을 복구합니다.
이러한 특징들이 안정적인 성능과 메모리 효율성을 제공합니다.
코드 예제
// 힙 정렬 구현
function heapSort(arr) {
const n = arr.length;
// 1단계: 배열을 Max Heap으로 변환 - O(n)
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
siftDown(arr, n, i);
}
// 2단계: 하나씩 최댓값을 추출하여 배열 끝에 배치 - O(n log n)
for (let i = n - 1; i > 0; i--) {
// 루트(최댓값)를 현재 마지막 위치와 교환
[arr[0], arr[i]] = [arr[i], arr[0]];
// 힙 크기를 1 줄이고 루트에서 sift-down
siftDown(arr, i, 0);
}
return arr;
}
function siftDown(arr, n, i) {
while (true) {
let largest = i;
const left = 2 * i + 1;
const 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;
[arr[i], arr[largest]] = [arr[largest], arr[i]];
i = largest;
}
}
// 사용 예시
const arr = [12, 11, 13, 5, 6, 7];
heapSort(arr);
console.log(arr); // [5, 6, 7, 11, 12, 13] - 오름차순 정렬
설명
이것이 하는 일: 힙 정렬은 두 단계로 작동합니다. 첫 번째 단계에서 배열을 힙으로 변환하고, 두 번째 단계에서 반복적으로 최댓값을 추출하여 정렬된 배열을 만듭니다.
핵심은 같은 배열 내에서 힙 영역과 정렬된 영역을 나누어 관리하는 것입니다. 첫 번째 단계에서는 heapify를 수행합니다.
Math.floor(n/2)-1부터 0까지 역순으로 각 노드에 대해 sift-down을 수행하여 전체 배열을 Max Heap으로 만듭니다. 이 과정은 O(n) 시간이 소요됩니다.
Heapify가 완료되면 배열의 첫 번째 요소(arr[0])가 최댓값이 됩니다. 이 단계는 한 번만 수행되며, 이후 과정의 기반이 됩니다.
두 번째 단계에서는 정렬의 핵심 루프가 실행됩니다. 배열의 마지막 인덱스부터 1까지(i = n-1 to 1) 반복하면서 다음을 수행합니다: (1) 루트(최댓값)와 i번째 위치를 교환합니다.
(2) 이제 i번째 이후는 정렬된 영역으로 간주합니다. (3) 힙 크기를 i로 줄여서(마지막 요소 제외) 루트에서 sift-down을 수행합니다.
이렇게 하면 교환으로 인해 깨진 힙 속성이 복구되고, 다시 루트에 현재 남은 요소 중 최댓값이 위치하게 됩니다. 세 번째 단계와 최종 결과: 이 과정을 n-1번 반복하면(첫 번째 요소는 자동으로 정렬됨), 배열 전체가 오름차순으로 정렬됩니다.
Max Heap을 사용하면 오름차순, Min Heap을 사용하면 내림차순이 됩니다. 시간복잡도는 heapify에 O(n), n번의 extractMax 각각에 O(log n)이므로 총 O(n + n log n) = O(n log n)입니다.
공간복잡도는 재귀 호출 스택을 제외하면 O(1)입니다(반복 방식 sift-down 사용 시). 여러분이 힙 정렬을 사용하면 메모리 제약이 있는 환경에서도 안정적인 성능을 얻을 수 있습니다.
특히 최악의 경우 성능이 중요한 시스템에서는 퀵 정렬보다 힙 정렬이 선호됩니다. 또한 외부 정렬에서 큰 파일을 작은 청크로 나누어 정렬할 때, 각 청크를 힙 정렬하면 메모리를 효율적으로 사용할 수 있습니다.
다만 힙 정렬은 불안정 정렬(같은 값의 순서가 보장되지 않음)이므로, 안정성이 필요한 경우에는 병합 정렬을 고려해야 합니다.
실전 팁
💡 힙 정렬은 캐시 친화적이지 않습니다. Sift-down 과정에서 멀리 떨어진 메모리 위치를 자주 접근하므로 캐시 미스가 많이 발생합니다. 이것이 실제로는 퀵 정렬보다 느린 이유입니다. 하지만 최악의 경우 보장이 필요하면 힙 정렬을 선택하세요.
💡 In-place 정렬을 위해 Max Heap을 사용하여 오름차순 정렬을 구현합니다. 만약 Min Heap을 사용하면 내림차순이 되는데, 이 경우 비교 연산을 반대로 하거나 최종적으로 배열을 역순으로 뒤집어야 합니다.
💡 힙 정렬은 불안정 정렬입니다. 같은 값을 가진 요소들의 원래 순서가 보존되지 않습니다. 안정성이 필요한 경우(예: 다중 키 정렬) 병합 정렬이나 Tim Sort를 사용하세요.
💡 성능 최적화를 위해 작은 배열(n < 10)에서는 삽입 정렬로 전환하는 하이브리드 접근을 고려하세요. Python의 Tim Sort처럼 상황에 맞는 알고리즘을 조합하면 실제 성능이 향상됩니다.
💡 디버깅 시 각 단계마다 힙 영역과 정렬된 영역을 시각화하면 도움이 됩니다. 예를 들어, [힙 영역 | 정렬된 영역] 형태로 로그를 출력하면 알고리즘의 진행 상황을 명확히 이해할 수 있습니다.
6. k번째 최댓값 찾기 - Heapify의 실용적 응용
시작하며
여러분이 대용량 데이터에서 k번째로 큰 값을 찾아야 하는 상황을 겪어본 적 있나요? 전체를 정렬하면 O(n log n)이 걸리지만, 사실 k번째 값 하나만 필요한데 전체 정렬은 낭비입니다.
이런 문제는 실무에서 매우 자주 발생합니다. 예를 들어, 상위 10개 검색 결과, 매출 상위 100개 제품, 평점 상위 50개 영화 등을 찾을 때, 전체 수백만 건을 정렬하는 것은 비효율적입니다.
바로 이럴 때 필요한 것이 힙을 사용한 k번째 최댓값 찾기입니다. Min Heap을 사용하면 O(n log k) 시간에, 또는 Max Heap과 부분 힙 정렬로 O(n + k log n) 시간에 찾을 수 있습니다.
개요
간단히 말해서, k번째 최댓값 찾기는 전체 정렬 없이 힙을 활용하여 효율적으로 k번째로 큰 값을 찾는 알고리즘입니다. 두 가지 주요 접근법이 있습니다: (1) 크기 k의 Min Heap을 유지하는 방법: 배열을 순회하면서 힙 크기가 k를 초과하면 최솟값을 제거합니다.
최종적으로 힙의 루트가 k번째 최댓값입니다. (2) Max Heap을 구성하고 k번 extractMax하는 방법: 전체 배열을 heapify한 후 k번 최댓값을 추출합니다.
실무에서는 상위 k개 아이템 추출, 중앙값 찾기, 스트리밍 데이터에서 실시간 순위 계산 등에 사용됩니다. 예를 들어, 실시간 검색 순위, 게임 리더보드, 추천 시스템의 상위 추천 아이템 선정 등에 활용됩니다.
기존에는 전체를 정렬한 후 인덱스로 접근했다면(O(n log n)), 이제는 힙을 사용하여 O(n log k) 또는 O(n + k log n)으로 개선할 수 있습니다. 핵심 특징은: (1) k가 n보다 훨씬 작을 때 매우 효율적입니다.
(2) 스트리밍 데이터에도 적용 가능합니다(크기 k의 Min Heap 사용). (3) 상위 k개 전체를 얻을 수도 있습니다.
이러한 특징들이 빅데이터 처리와 실시간 시스템에서 필수적인 기법으로 만듭니다.
코드 예제
// 방법 1: 크기 k의 Min Heap 사용 - O(n log k)
function findKthLargest1(arr, k) {
const minHeap = [];
for (let num of arr) {
// 힙에 요소 추가
minHeap.push(num);
minHeapSiftUp(minHeap, minHeap.length - 1);
// 힙 크기가 k를 초과하면 최솟값(루트) 제거
if (minHeap.length > k) {
// 루트와 마지막 요소 교환 후 제거
minHeap[0] = minHeap.pop();
if (minHeap.length > 0) {
minHeapSiftDown(minHeap, minHeap.length, 0);
}
}
}
// 힙의 루트가 k번째 최댓값
return minHeap[0];
}
// 방법 2: Max Heap 구성 후 k번 추출 - O(n + k log n)
function findKthLargest2(arr, k) {
const n = arr.length;
// Max Heap 구성
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
maxHeapSiftDown(arr, n, i);
}
// k-1번 최댓값 제거
let heapSize = n;
for (let i = 0; i < k - 1; i++) {
[arr[0], arr[heapSize - 1]] = [arr[heapSize - 1], arr[0]];
heapSize--;
maxHeapSiftDown(arr, heapSize, 0);
}
// k번째 최댓값 반환
return arr[0];
}
// Min Heap 헬퍼 함수들
function minHeapSiftUp(arr, i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (arr[i] >= arr[parent]) break;
[arr[i], arr[parent]] = [arr[parent], arr[i]];
i = parent;
}
}
function minHeapSiftDown(arr, n, i) {
while (true) {
let smallest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest]) smallest = left;
if (right < n && arr[right] < arr[smallest]) smallest = right;
if (smallest === i) break;
[arr[i], arr[smallest]] = [arr[smallest], arr[i]];
i = smallest;
}
}
// 사용 예시
const arr = [3, 2, 1, 5, 6, 4];
console.log(findKthLargest1(arr, 2)); // 5 (2번째 최댓값)
console.log(findKthLargest2([3, 2, 1, 5, 6, 4], 3)); // 4 (3번째 최댓값)
설명
이것이 하는 일: k번째 최댓값 찾기는 전체 데이터를 정렬하지 않고도 특정 순위의 값을 효율적으로 찾습니다. 두 가지 방법이 있으며, 상황에 따라 적합한 방법을 선택합니다.
첫 번째 방법(크기 k의 Min Heap)은 메모리 효율적이고 스트리밍 데이터에 적합합니다. 작동 원리는 다음과 같습니다: (1) 빈 Min Heap으로 시작합니다.
(2) 배열의 각 요소를 순회하면서 힙에 추가합니다. (3) 힙 크기가 k를 초과하면 최솟값(루트)을 제거합니다.
이렇게 하면 힙에는 항상 가장 큰 k개 요소만 남습니다. (4) 모든 요소를 처리한 후, 힙의 루트(최솟값)가 k번째 최댓값입니다.
왜냐하면 힙에는 상위 k개가 있고, 그중 최솟값이 k번째이기 때문입니다. 시간복잡도는 n개 요소 각각에 대해 O(log k) 삽입과 제거를 수행하므로 O(n log k)입니다.
공간복잡도는 O(k)로, k가 작으면 매우 메모리 효율적입니다. 두 번째 방법(Max Heap)은 구현이 단순하고, 상위 k개 전체가 필요할 때 유용합니다.
작동 원리는: (1) 전체 배열을 Max Heap으로 변환합니다(O(n)). (2) k-1번 extractMax를 수행하여 1번째부터 k-1번째까지 제거합니다.
(3) 남은 루트가 k번째 최댓값입니다. 시간복잡도는 heapify에 O(n), k-1번의 extractMax 각각에 O(log n)이므로 O(n + k log n)입니다.
k가 작을 때(k << n) 이 방법도 효율적이며, 특히 k개 최댓값 전체를 추출해야 할 때는 이 방법이 자연스럽습니다. 세 번째 단계와 최종 결과: 어떤 방법을 선택할지는 상황에 따라 다릅니다.
k가 매우 작고(k << log n) 메모리가 제한되어 있으면 방법 1이 유리합니다(O(n log k), 공간 O(k)). k가 n에 가까우면 방법 2가 유리합니다(O(n + k log n)이 O(n log k)보다 작음).
또한 데이터가 스트리밍 형태로 들어오면 방법 1만 가능합니다. 실무에서는 대부분 k가 작으므로(상위 10개, 100개 등) 방법 1이 널리 사용됩니다.
여러분이 이 알고리즘을 사용하면 빅데이터 처리에서 큰 이점을 얻습니다. 예를 들어, 1억 개의 제품 중 매출 상위 100개를 찾을 때, 전체 정렬은 O(n log n) ≈ 26.6억 연산이지만, Min Heap 방식은 O(n log k) ≈ 6.6억 연산으로 약 4배 빠릅니다.
또한 메모리도 O(n) 대신 O(k)만 사용하여 크게 절약됩니다.
실전 팁
💡 k가 n/2보다 크면 n-k번째 최솟값을 찾는 것으로 문제를 변환하세요. 예를 들어, 100개 중 95번째 최댓값은 6번째 최솟값과 같습니다. 이렇게 하면 시간복잡도를 최적화할 수 있습니다.
💡 JavaScript에서 Min Heap을 직접 구현하는 대신, 라이브러리(예: heap-js, priorityqueuejs)를 사용하면 개발 속도가 빨라집니다. 단, 프로덕션에서는 라이브러리의 유지보수 상태와 성능을 확인하세요.
💡 스트리밍 데이터에서 실시간 k번째 최댓값을 유지하려면 크기 k의 Min Heap을 계속 업데이트하세요. 새 데이터가 들어올 때마다 O(log k)에 처리되므로, 실시간 리더보드나 추천 시스템에 적합합니다.
💡 상위 k개 전체가 필요하면 방법 1 사용 후 힙의 모든 요소를 추출하거나, 방법 2에서 추출한 값들을 저장하세요. 추출된 값들은 이미 내림차순으로 정렬되어 있습니다.
💡 중앙값 찾기에도 힙을 활용할 수 있습니다. Max Heap(하위 절반)과 Min Heap(상위 절반) 두 개를 유지하면, 동적으로 추가되는 데이터의 중앙값을 O(log n)에 계산할 수 있습니다. 이는 스트리밍 통계 계산에 매우 유용합니다.
7. 힙의 시간복잡도 분석 - 왜 Heapify는 O(n)인가
시작하며
여러분이 heapify의 시간복잡도를 분석할 때, 직관적으로 n개 노드에 각각 O(log n) sift-down을 수행하므로 O(n log n)이라고 생각한 적 있나요? 그런데 실제로는 O(n)이라고 하니 혼란스러울 것입니다.
이런 착각은 알고리즘을 처음 배울 때 흔히 발생하며, 시간복잡도를 정확히 이해하지 못하면 알고리즘 선택을 잘못할 수 있습니다. 예를 들어, 초기 힙 구성이 필요한 상황에서 요소를 하나씩 삽입하는 비효율적인 방법을 선택할 수 있습니다.
바로 이럴 때 필요한 것이 정확한 시간복잡도 분석입니다. Heapify가 O(n)인 이유를 이해하면, 알고리즘을 더 효율적으로 선택하고 최적화할 수 있습니다.
개요
간단히 말해서, heapify의 시간복잡도가 O(n)인 이유는 대부분의 노드가 트리의 하위 레벨에 있어서 sift-down 거리가 짧기 때문입니다. 완전 이진 트리의 중요한 속성이 있습니다: 높이 h인 완전 이진 트리에서 레벨 i(0부터 시작)의 노드 수는 최대 2^i개이고, 각 노드의 sift-down 최대 거리는 h-i입니다.
따라서 리프 노드(절반)는 sift-down이 0, 그 위 레벨(1/4)은 최대 1번, 그 위(1/8)는 최대 2번만 내려갑니다. 이를 수학적으로 합산하면 O(n)이 됩니다.
실무에서는 대용량 데이터의 초기 힙 구성 시 이 차이가 매우 중요합니다. n이 백만 개라면 O(n log n)과 O(n)의 차이는 약 20배입니다.
기존 생각: n개 노드 × O(log n) = O(n log n). 실제: 대부분의 노드는 짧은 거리만 이동하므로 평균 O(1), 총 O(n).
핵심 특징은: (1) 완전 이진 트리의 노드 분포가 핵심입니다. (2) Bottom-up 방식이 Top-down보다 효율적입니다.
(3) 수학적 증명은 등비급수 합을 사용합니다. 이러한 특징들이 heapify를 매우 효율적인 초기화 방법으로 만듭니다.
코드 예제
// 시간복잡도 분석을 위한 Heapify with Counter
function heapifyWithCount(arr) {
const n = arr.length;
let siftDownCount = 0; // Sift-down 호출 횟수
let comparisonCount = 0; // 비교 연산 횟수
// 마지막 부모 노드부터 역순으로
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
siftDownCount++;
const [comparisons] = siftDownWithCount(arr, n, i);
comparisonCount += comparisons;
}
return {
array: arr,
siftDownCalls: siftDownCount,
comparisons: comparisonCount,
theoretical: n * Math.log2(n), // 잘못된 추정
actual: n // 실제 복잡도
};
}
function siftDownWithCount(arr, n, i) {
let comparisons = 0;
while (true) {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n) {
comparisons++; // 비교 카운트
if (arr[left] > arr[largest]) {
largest = left;
}
}
if (right < n) {
comparisons++; // 비교 카운트
if (arr[right] > arr[largest]) {
largest = right;
}
}
if (largest === i) break;
[arr[i], arr[largest]] = [arr[largest], arr[i]];
i = largest;
}
return [comparisons];
}
// 실험: 다양한 크기에서 비교 연산 측정
const sizes = [10, 100, 1000, 10000];
for (let size of sizes) {
const arr = Array.from({length: size}, () => Math.floor(Math.random() * 1000));
const result = heapifyWithCount([...arr]);
console.log(`n=${size}: comparisons=${result.comparisons}, n=${size}, n*log(n)=${(size * Math.log2(size)).toFixed(0)}`);
// 결과는 comparisons가 n에 가깝고 n*log(n)보다 훨씬 작음을 보여줌
}
설명
이것이 하는 일: heapify의 시간복잡도를 정확히 분석하여 O(n)임을 증명합니다. 이는 알고리즘 효율성을 이해하는 데 매우 중요합니다.
첫 번째 단계에서는 완전 이진 트리의 구조를 이해해야 합니다. 높이 h인 완전 이진 트리는 약 n = 2^(h+1) - 1개의 노드를 가집니다.
각 레벨 i(루트가 레벨 0)는 최대 2^i개의 노드를 가집니다. 중요한 점은 노드의 절반이 리프 노드(마지막 레벨)에 있다는 것입니다.
구체적으로, 레벨 h에는 약 n/2개, 레벨 h-1에는 약 n/4개, 레벨 h-2에는 약 n/8개 노드가 있습니다. 두 번째 단계에서는 각 레벨의 노드가 sift-down으로 이동할 수 있는 최대 거리를 계산합니다.
레벨 i의 노드는 최대 h-i만큼 아래로 이동할 수 있습니다. 즉, 리프 노드(레벨 h)는 0번, 그 위 레벨(h-1)은 최대 1번, 그 위(h-2)는 최대 2번 이동합니다.
따라서 총 작업량은 다음과 같이 계산됩니다: (n/2)×0 + (n/4)×1 + (n/8)×2 + (n/16)×3 + ... 이는 등비급수의 형태입니다.
세 번째 단계와 최종 결과: 위 합을 계산하면 n × Σ(i/2^i) (i=1 to h)가 됩니다. 수학적으로 Σ(i/2^i)는 2에 수렴하므로(등비급수 공식), 총 작업량은 약 2n, 즉 O(n)입니다.
엄밀한 증명은 다음과 같습니다: S = Σ(i=0 to h) [(n/2^(i+1)) × i]. 2^(h+1) ≈ n을 사용하고 정리하면 S ≤ n × Σ(i/2^i) = n × 2 = 2n = O(n)입니다.
반면, 요소를 하나씩 삽입하는 Top-down 방식은 각 삽입에 평균 O(log n)이 걸려 총 O(n log n)입니다. 여러분이 이 분석을 이해하면 알고리즘 선택에서 실수를 피할 수 있습니다.
초기 힙 구성이 필요할 때는 항상 heapify를 사용하고, 요소를 하나씩 삽입하지 마세요. 예를 들어, 100만 개 요소로 힙을 만들 때 heapify는 약 200만 연산, 하나씩 삽입은 약 2000만 연산으로 10배 차이가 납니다.
또한 힙 정렬의 총 시간복잡도는 heapify O(n) + n번 extractMax O(n log n) = O(n log n)이므로, heapify가 O(n)인 것이 중요합니다.
실전 팁
💡 Heapify는 Bottom-up(마지막 부모부터 역순)을 사용하고, 요소 하나씩 삽입은 Top-down(루트부터 삽입)입니다. 초기 구성에는 항상 Bottom-up이 효율적이며, 이것이 heapify를 사용해야 하는 이유입니다.
💡 실험적으로 검증하려면 다양한 크기의 배열에서 비교 연산 횟수를 측정하세요. n이 커질수록 비교 횟수가 n에 비례하고 n log n보다 훨씬 적음을 확인할 수 있습니다.
💡 인터뷰에서 "heapify는 O(n log n) 아닌가요?"라는 질문을 받으면, 완전 이진 트리의 노드 분포와 sift-down 거리의 관계를 설명하세요. 이는 알고리즘에 대한 깊은 이해를 보여줍니다.
💡 다른 자료구조의 초기화 비용도 비교해보세요. 예를 들어, 이진 탐색 트리는 정렬된 배열로 O(n)에 균형 트리를 만들 수 있지만(전위 순회), 정렬되지 않은 배열로는 O(n log n)이 필요합니다. 힙은 정렬 여부와 무관하게 O(n)이라는 장점이 있습니다.
💡 공간복잡도도 고려하세요. Heapify는 in-place로 O(1) 추가 메모리만 사용합니다(재귀 스택 제외). 반면 병합 정렬 기반 초기화는 O(n) 추가 메모리가 필요합니다. 메모리 제약이 있는 환경에서는 이것도 중요한 선택 요인입니다.
8. 우선순위 큐 구현 - 힙의 대표적 응용
시작하며
여러분이 작업을 우선순위에 따라 처리해야 하는 시스템을 구현할 때, 단순 배열이나 정렬된 리스트로는 삽입이나 추출 중 하나가 O(n)이 걸려 비효율적인 경험을 한 적 있나요? 우선순위가 동적으로 변하거나 작업이 계속 추가되는 상황에서는 성능 문제가 심각합니다.
이런 문제는 운영체제의 프로세스 스케줄링, 네트워크 라우터의 패킷 전송, 게임 서버의 이벤트 처리, 다익스트라 알고리즘 등 실제 개발 현장에서 핵심적입니다. 효율적인 우선순위 큐가 없으면 시스템 전체의 성능이 저하됩니다.
바로 이럴 때 필요한 것이 힙 기반 우선순위 큐입니다. 삽입과 추출 모두 O(log n)으로 처리하며, 최우선 요소는 O(1)에 확인할 수 있어 실시간 시스템에 이상적입니다.
개요
간단히 말해서, 우선순위 큐는 각 요소가 우선순위를 가지며, 항상 최우선 요소가 먼저 처리되는 추상 자료구조로, 힙으로 효율적으로 구현됩니다. 우선순위 큐는 큐와 달리 FIFO가 아니라 우선순위 순서로 요소를 처리합니다.
힙을 사용하면 주요 연산의 시간복잡도가 다음과 같습니다: insert O(log n), extractMax/extractMin O(log n), peek O(1), heapify(초기 구성) O(n). 실무에서는 작업 스케줄링(운영체제, 웹 서버), 그래프 알고리즘(다익스트라, 프림), 이벤트 기반 시뮬레이션, 허프만 코딩, k-way 병합 등 다양한 곳에 사용됩니다.
예를 들어, Node.js의 이벤트 루프는 내부적으로 우선순위 큐를 사용하여 타이머 이벤트를 관리합니다. 기존 구현과 비교하면: 정렬되지 않은 배열은 insert O(1), extract O(n), 정렬된 배열은 insert O(n), extract O(1), 힙은 양쪽 모두 O(log n)으로 균형 잡혀 있습니다.
핵심 특징은: (1) 동적 데이터에 최적화되어 있습니다(계속 삽입/추출). (2) 최우선 요소에만 관심이 있을 때 효율적입니다(전체 정렬 불필요).
(3) 커스텀 비교 함수로 다양한 우선순위 정의 가능합니다. 이러한 특징들이 우선순위 큐를 실시간 시스템의 핵심 자료구조로 만듭니다.
코드 예제
// 우선순위 큐 클래스 (Max Heap 기반)
class PriorityQueue {
constructor(compareFn = (a, b) => a - b) {
this.heap = [];
this.compare = compareFn; // 양수면 a가 높은 우선순위
}
// 요소 개수 반환
size() {
return this.heap.length;
}
// 비어있는지 확인
isEmpty() {
return this.heap.length === 0;
}
// 최우선 요소 확인 (제거하지 않음) - O(1)
peek() {
if (this.isEmpty()) return null;
return this.heap[0];
}
// 요소 삽입 - O(log n)
insert(value) {
this.heap.push(value);
this._siftUp(this.heap.length - 1);
}
// 최우선 요소 추출 - O(log n)
extract() {
if (this.isEmpty()) return null;
if (this.size() === 1) return this.heap.pop();
const max = this.heap[0];
this.heap[0] = this.heap.pop();
this._siftDown(0);
return max;
}
// Sift-up 연산
_siftUp(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.compare(this.heap[i], this.heap[parent]) <= 0) break;
[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
i = parent;
}
}
// Sift-down 연산
_siftDown(i) {
const n = this.heap.length;
while (true) {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && this.compare(this.heap[left], this.heap[largest]) > 0) {
largest = left;
}
if (right < n && this.compare(this.heap[right], this.heap[largest]) > 0) {
largest = right;
}
if (largest === i) break;
[this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
i = largest;
}
}
}
// 사용 예시 1: 숫자 우선순위 큐
const pq = new PriorityQueue();
pq.insert(5);
pq.insert(3);
pq.insert(7);
pq.insert(1);
console.log(pq.extract()); // 7
console.log(pq.extract()); // 5
// 사용 예시 2: 객체 우선순위 큐 (작업 스케줄링)
const taskQueue = new PriorityQueue((a, b) => a.priority - b.priority);
taskQueue.insert({ name: 'Task A', priority: 2 });
taskQueue.insert({ name: 'Task B', priority: 5 });
taskQueue.insert({ name: 'Task C', priority: 1 });
console.log(taskQueue.extract()); // { name: 'Task B', priority: 5 }
설명
이것이 하는 일: 우선순위 큐는 요소들을 우선순위 순서로 관리하여, 항상 최우선 요소를 빠르게 추출할 수 있게 합니다. 힙을 내부 구조로 사용하여 효율성을 보장합니다.
첫 번째 단계에서는 우선순위 큐의 핵심 연산들을 이해해야 합니다: (1) insert(value): 새 요소를 추가합니다. 배열 끝에 추가 후 sift-up으로 올바른 위치로 이동시킵니다.
(2) extract(): 최우선 요소를 제거하고 반환합니다. 루트를 반환하고 마지막 요소를 루트로 이동 후 sift-down으로 힙을 복구합니다.
(3) peek(): 최우선 요소를 제거하지 않고 확인만 합니다. 단순히 heap[0]을 반환하므로 O(1)입니다.
(4) isEmpty(), size(): 상태 확인 메서드들입니다. 이들 연산의 조합으로 다양한 알고리즘을 구현할 수 있습니다.
두 번째 단계에서는 커스텀 비교 함수(compareFn)의 중요성을 이해해야 합니다. 기본적으로 숫자를 비교하지만(a - b), 객체의 특정 속성으로 우선순위를 정의할 수 있습니다.
예를 들어, 작업 객체의 priority 필드로 비교하거나, 다익스트라 알고리즘에서 거리(distance)로 비교합니다. 비교 함수는 a가 b보다 높은 우선순위면 양수, 같으면 0, 낮으면 음수를 반환해야 합니다.
이 설계는 JavaScript의 Array.sort()와 유사하여 일관성이 있고, 다양한 타입의 데이터를 우선순위 큐에 저장할 수 있게 합니다. 세 번째 단계와 최종 결과: 클래스 기반 구현은 캡슐화와 재사용성을 제공합니다.
내부 배열(heap)은 private으로 취급하고, 외부에서는 insert, extract 등 공개 메서드만 사용합니다. _siftUp, _siftDown은 내부 헬퍼 메서드로 언더스코어로 표시합니다(JavaScript에는 진짜 private이 없지만 관례).
이 구조는 유지보수가 쉽고, 여러 우선순위 큐 인스턴스를 독립적으로 사용할 수 있습니다. 실무에서는 이 클래스를 기반으로 특정 도메인에 맞게 확장할 수 있습니다.
여러분이 이 우선순위 큐를 사용하면 복잡한 스케줄링 문제를 간단히 해결할 수 있습니다. 예를 들어, 웹 서버에서 VIP 사용자 요청을 우선 처리하려면, 요청 객체에 우선순위를 부여하고 우선순위 큐에 넣으면 됩니다.
게임 서버에서 여러 이벤트(몬스터 스폰, 아이템 드롭, 플레이어 액션)를 타임스탬프 순서로 처리하는 이벤트 루프도 우선순위 큐로 구현됩니다. 또한 다익스트라 알고리즘에서 다음 방문할 노드를 선택할 때 우선순위 큐를 사용하면 O((V+E) log V)의 효율적인 구현이 가능합니다.
실전 팁
💡 JavaScript에는 내장 우선순위 큐가 없으므로 직접 구현하거나 라이브러리(heap-js, priorityqueuejs)를 사용하세요. TypeScript로 구현하면 타입 안전성이 향상됩니다.
💡 Min Heap이 필요하면 비교 함수를 반대로 하세요: (a, b) => b - a. 또는 Min Heap 버전 클래스를 따로 만들거나, 생성자에서 힙 타입을 지정하게 할 수 있습니다.
💡 우선순위가 같은 요소들의 순서는 보장되지 않습니다(불안정). 순서가 중요하면 우선순위에 타임스탬프나 시퀀스 번호를 포함시켜 tie-breaking 규칙을 만드세요.
💡 대량의 초기 데이터로 우선순위 큐를 만들 때는 하나씩 insert하지 말고, 배열을 받아 heapify하는 생성자를 추가하세요. 이렇게 하면 O(n log n) 대신 O(n)에 초기화됩니다.
💡 디버깅을 위해 힙을 시각화하는 메서드를 추가하면 유용합니다. 예를 들어, 레벨 단위로 노드를 출력하는 printHeap() 메서드를 만들면 힙 구조를 쉽게 확인할 수 있습니다.