이미지 로딩 중...
AI Generated
2025. 11. 8. · 4 Views
Heapify로 배열을 힙으로 변환하는 완벽 가이드
배열을 효율적으로 힙 자료구조로 변환하는 Heapify 알고리즘을 배웁니다. 시간 복잡도 O(n)으로 힙을 구축하는 방법과 실무에서 우선순위 큐를 구현하는 핵심 기법을 다룹니다.
목차
- 힙(Heap) 자료구조의 이해 - 완전 이진 트리의 특별한 형태
- Heapify Up (상향 조정) - 새 요소를 올바른 위치로
- Heapify Down (하향 조정) - 루트 제거 후 복구
- Build Heap (힙 구축) - 배열을 O(n)에 힙으로 변환
- 힙 정렬 (Heap Sort) - 정렬 알고리즘으로 활용
- 우선순위 큐 구현 - 힙의 실전 활용
- Top K 문제 해결 - 힙을 활용한 효율적인 선택
- 중간값 찾기 (Median Finding) - 두 개의 힙 활용
1. 힙(Heap) 자료구조의 이해 - 완전 이진 트리의 특별한 형태
시작하며
여러분이 실시간 이벤트 처리 시스템을 개발하거나, 작업 스케줄링을 구현할 때 이런 고민을 해본 적 있나요? "수천 개의 작업 중에서 항상 가장 우선순위가 높은 작업을 빠르게 찾아야 하는데, 어떻게 효율적으로 관리할 수 있을까?" 배열을 정렬하면 O(n log n)이 걸리고, 매번 최솟값을 찾으려면 O(n)이 필요합니다.
이런 문제는 실제 개발 현장에서 자주 발생합니다. 예를 들어, Dijkstra 알고리즘으로 최단 경로를 찾거나, 실시간 채팅 앱에서 메시지 우선순위를 관리하거나, OS의 프로세스 스케줄링을 구현할 때 말이죠.
일반 배열이나 리스트로는 삽입과 삭제, 최솟값 검색을 모두 효율적으로 처리하기 어렵습니다. 바로 이럴 때 필요한 것이 힙(Heap) 자료구조입니다.
힙은 O(log n) 시간에 삽입과 삭제를 수행하면서도 O(1) 시간에 최솟값(또는 최댓값)을 찾을 수 있는 완전 이진 트리 기반의 자료구조입니다.
개요
간단히 말해서, 힙은 부모 노드가 항상 자식 노드보다 작거나 같은(최소 힙의 경우) 값을 가지는 완전 이진 트리입니다. 왜 이 자료구조가 필요한지 실무 관점에서 설명하면, 우선순위 큐를 구현할 때 가장 효율적인 방법이기 때문입니다.
예를 들어, 병원 응급실에서 환자의 위급도에 따라 치료 순서를 정하거나, 네트워크 라우터에서 패킷의 우선순위를 관리하거나, 게임 서버에서 이벤트 처리 순서를 결정할 때 매우 유용합니다. 전통적인 방법과의 비교를 해보면, 기존에는 정렬된 배열이나 연결 리스트를 사용해서 우선순위 큐를 구현했다면, 이제는 힙을 사용해서 삽입 O(log n), 삭제 O(log n), 최솟값 조회 O(1)의 성능을 얻을 수 있습니다.
힙의 핵심 특징은 세 가지입니다. 첫째, 완전 이진 트리 구조라서 배열로 효율적으로 표현할 수 있습니다.
둘째, 힙 속성(부모가 자식보다 작거나 큼)을 항상 유지합니다. 셋째, 루트 노드에 항상 최솟값(또는 최댓값)이 위치합니다.
이러한 특징들이 중요한 이유는 메모리 효율성과 빠른 접근 시간을 동시에 보장하기 때문입니다.
코드 예제
// 최소 힙을 구현하는 MinHeap 클래스
class MinHeap {
constructor() {
this.heap = []; // 배열로 힙을 표현
}
// 부모 노드의 인덱스를 반환
getParentIndex(index) {
return Math.floor((index - 1) / 2);
}
// 왼쪽 자식 노드의 인덱스를 반환
getLeftChildIndex(index) {
return 2 * index + 1;
}
// 오른쪽 자식 노드의 인덱스를 반환
getRightChildIndex(index) {
return 2 * index + 2;
}
// 두 노드의 값을 교환
swap(index1, index2) {
[this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
}
}
설명
이것이 하는 일: 힙은 우선순위 기반 데이터 관리를 위한 트리 구조로, 항상 가장 중요한 요소에 빠르게 접근할 수 있게 해줍니다. 첫 번째로, 힙의 구조를 살펴보면 완전 이진 트리 형태를 띱니다.
완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워지는 트리입니다. 이렇게 하는 이유는 배열로 표현했을 때 인덱스 계산이 간단해지기 때문입니다.
부모의 인덱스가 i라면, 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2가 됩니다. 그 다음으로, 힙 속성(heap property)이 핵심입니다.
최소 힙에서는 모든 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 합니다. 이 속성이 유지되면 루트 노드에 항상 최솟값이 위치하게 됩니다.
반대로 최대 힙에서는 부모가 자식보다 크거나 같아야 하므로 루트에 최댓값이 옵니다. 세 번째로, 배열 표현의 장점을 이해해야 합니다.
트리 구조를 포인터 없이 배열로만 표현할 수 있어서 메모리 오버헤드가 없고, 인덱스 계산으로 부모와 자식에 바로 접근할 수 있습니다. 예를 들어, 인덱스 5의 부모는 (5-1)/2 = 2, 자식은 11과 12입니다.
여러분이 이 자료구조를 사용하면 우선순위 큐, 힙 정렬, 중간값 찾기 같은 다양한 알고리즘 문제를 효율적으로 해결할 수 있습니다. 실무에서는 작업 스케줄링, 이벤트 드리븐 시뮬레이션, 그래프 알고리즘(최단 경로, 최소 신장 트리) 등에서 널리 활용됩니다.
특히 JavaScript에서는 직접 구현해야 하지만, Python의 heapq나 Java의 PriorityQueue처럼 다른 언어에서는 표준 라이브러리로 제공됩니다.
실전 팁
💡 힙은 완전 정렬이 아닙니다. 형제 노드 간에는 순서가 보장되지 않으므로, 정렬된 배열이 필요하다면 힙 정렬을 따로 수행해야 합니다.
💡 최소 힙과 최대 힙을 동시에 사용하면 중간값을 O(1)에 찾을 수 있습니다. 작은 값의 절반은 최대 힙에, 큰 값의 절반은 최소 힙에 저장하는 것이 핵심입니다.
💡 실무에서는 커스텀 비교 함수를 지원하도록 구현하세요. 객체의 특정 속성으로 우선순위를 정하거나, 복잡한 비교 로직을 적용할 수 있어야 합니다.
💡 힙 크기가 고정되어 있다면 배열 크기를 미리 할당하세요. 동적 배열의 재할당 오버헤드를 피할 수 있어 성능이 향상됩니다.
💡 디버깅할 때는 힙을 트리 형태로 시각화하세요. 배열로는 힙 속성 위반을 찾기 어렵지만, 트리로 그리면 한눈에 파악됩니다.
2. Heapify Up (상향 조정) - 새 요소를 올바른 위치로
시작하며
여러분이 힙에 새로운 요소를 삽입할 때 이런 문제를 마주칩니다. "새 요소를 어디에 넣어야 힙 속성이 유지될까?" 그냥 아무 곳에나 넣으면 부모-자식 관계가 깨져서 더 이상 힙이 아니게 됩니다.
이런 문제는 힙의 핵심 연산인 삽입(insert)을 구현할 때 반드시 해결해야 합니다. 예를 들어, 우선순위 큐에 새로운 작업을 추가하거나, 실시간으로 데이터가 들어오는 스트리밍 환경에서 힙을 유지 관리해야 할 때 말이죠.
잘못 삽입하면 이후 모든 연산의 정확성이 무너집니다. 바로 이럴 때 필요한 것이 Heapify Up(상향 조정) 알고리즘입니다.
새 요소를 맨 끝에 추가한 후, 부모와 비교하면서 힙 속성이 만족될 때까지 위로 올려가는 방식으로 O(log n) 시간에 올바른 위치를 찾습니다.
개요
간단히 말해서, Heapify Up은 새로 삽입된 요소를 부모와 반복적으로 비교하면서 힙 속성이 만족될 때까지 위로 올리는 과정입니다. 왜 이 알고리즘이 필요한지 실무 관점에서 설명하면, 동적으로 데이터가 추가되는 상황에서 힙을 효율적으로 유지하기 위해서입니다.
예를 들어, 온라인 게임에서 플레이어가 실시간으로 점수를 올릴 때 리더보드를 업데이트하거나, 주식 거래 시스템에서 새로운 주문이 들어올 때 가격 우선순위를 관리하는 경우에 매우 유용합니다. 전통적인 방법과의 비교를 해보면, 기존에는 새 요소를 추가한 후 전체를 다시 정렬했다면(O(n log n)), 이제는 Heapify Up으로 O(log n)만에 힙 속성을 복구할 수 있습니다.
Heapify Up의 핵심 특징은 두 가지입니다. 첫째, 완전 이진 트리의 높이인 log n만큼만 비교하므로 효율적입니다.
둘째, 삽입 위치를 맨 끝으로 고정함으로써 완전 이진 트리 구조를 유지합니다. 이러한 특징들이 중요한 이유는 힙의 시간 복잡도 보장과 구조적 안정성을 동시에 제공하기 때문입니다.
코드 예제
// MinHeap 클래스에 추가되는 메서드들
class MinHeap {
// ... 이전 코드 ...
// 새로운 값을 힙에 삽입
insert(value) {
this.heap.push(value); // 배열 끝에 새 요소 추가
this.heapifyUp(this.heap.length - 1); // 상향 조정 시작
}
// 특정 인덱스부터 위로 올라가며 힙 속성 복구
heapifyUp(index) {
while (index > 0) { // 루트에 도달할 때까지 반복
const parentIndex = this.getParentIndex(index);
// 부모보다 크거나 같으면 힙 속성이 만족되므로 종료
if (this.heap[index] >= this.heap[parentIndex]) {
break;
}
// 부모보다 작으면 교환하고 계속 위로
this.swap(index, parentIndex);
index = parentIndex;
}
}
}
설명
이것이 하는 일: Heapify Up은 힙의 맨 끝에 추가된 새 요소를 부모 노드들과 비교하면서 적절한 위치로 이동시켜 힙의 구조적 속성을 유지합니다. 첫 번째로, 삽입 과정을 이해해야 합니다.
새 요소는 항상 배열의 맨 끝에 추가됩니다. 이렇게 하는 이유는 완전 이진 트리의 속성을 유지하기 위해서입니다.
만약 중간에 삽입하면 트리가 불완전해져서 힙의 기본 전제가 무너집니다. 끝에 추가하면 트리의 마지막 레벨 왼쪽부터 채워지는 규칙을 자동으로 따르게 됩니다.
그 다음으로, 상향 이동 과정이 실행됩니다. 삽입된 요소의 인덱스에서 시작해서 부모 노드와 값을 비교합니다.
최소 힙의 경우, 자식이 부모보다 작으면 힙 속성에 위배되므로 두 값을 교환합니다. 교환 후에는 부모의 위치로 올라가서 다시 그 부모와 비교하는 과정을 반복합니다.
세 번째로, 종료 조건을 파악해야 합니다. 두 가지 경우에 Heapify Up이 멈춥니다.
첫째, 현재 노드가 부모보다 크거나 같으면 힙 속성이 만족되므로 중단합니다. 둘째, 루트 노드(인덱스 0)에 도달하면 더 이상 올라갈 곳이 없으므로 종료합니다.
이 두 조건이 알고리즘의 정확성과 종료를 보장합니다. 마지막으로, 시간 복잡도를 분석하면 최악의 경우 루트까지 올라가야 하므로 트리의 높이인 O(log n)입니다.
실제로는 평균적으로 더 적은 비교로 끝나는 경우가 많습니다. 예를 들어, 삽입된 값이 이미 적절한 위치에 가까우면 몇 번의 비교만으로 종료됩니다.
여러분이 이 알고리즘을 사용하면 힙에 요소를 빠르게 추가하면서도 힙의 무결성을 유지할 수 있습니다. 실무에서는 이벤트 큐에 새 이벤트 추가, 우선순위 작업 스케줄러에 작업 등록, 실시간 데이터 스트림에서 상위 K개 요소 추적 등에 활용됩니다.
특히 삽입이 빈번한 시스템에서 Heapify Up의 효율성이 전체 성능을 좌우합니다.
실전 팁
💡 반복문 대신 재귀로 구현할 수도 있지만, 반복문이 스택 오버플로우 위험이 없어 더 안전합니다. 힙 크기가 클 때는 반복문을 선택하세요.
💡 삽입 전에 배열 용량을 체크하세요. 동적 배열의 크기가 부족하면 재할당이 일어나 성능 저하가 발생할 수 있습니다.
💡 여러 요소를 한 번에 삽입할 때는 각각 insert를 호출하는 것보다 배열에 모두 추가한 후 heapify를 한 번만 하는 게 더 효율적입니다(다음 카드 참조).
💡 디버깅 시 각 교환마다 힙을 출력해보세요. 요소가 어떻게 위로 이동하는지 시각적으로 확인하면 이해가 쉽습니다.
💡 같은 값이 여러 개 있어도 알고리즘은 정상 작동합니다. 부모와 같으면 교환하지 않으므로 안정적입니다.
3. Heapify Down (하향 조정) - 루트 제거 후 복구
시작하며
여러분이 힙에서 최솟값(루트)을 제거한 후 이런 상황에 직면합니다. "루트가 사라진 빈자리를 어떻게 채우고, 힙 속성을 다시 만족시킬까?" 단순히 다음 노드를 루트로 올리면 트리 구조가 깨지거나 힙 속성이 위배됩니다.
이런 문제는 힙의 또 다른 핵심 연산인 삭제(delete/extract)를 구현할 때 반드시 해결해야 합니다. 예를 들어, 우선순위 큐에서 가장 높은 우선순위 작업을 꺼내서 처리하거나, 힙 정렬에서 정렬된 요소를 하나씩 추출할 때 말이죠.
제거 후 힙을 제대로 복구하지 않으면 다음 연산들이 모두 잘못된 결과를 반환합니다. 바로 이럴 때 필요한 것이 Heapify Down(하향 조정) 알고리즘입니다.
마지막 요소를 루트로 옮긴 후, 자식들과 비교하면서 힙 속성이 만족될 때까지 아래로 내려가는 방식으로 O(log n) 시간에 힙을 재구성합니다.
개요
간단히 말해서, Heapify Down은 루트에 위치한 요소를 자식들과 반복적으로 비교하면서 힙 속성이 만족될 때까지 아래로 내리는 과정입니다. 왜 이 알고리즘이 필요한지 실무 관점에서 설명하면, 우선순위가 가장 높은 요소를 처리한 후 다음 요소에 빠르게 접근하기 위해서입니다.
예를 들어, 운영체제의 프로세스 스케줄러에서 가장 높은 우선순위 프로세스를 실행하고 다음 프로세스를 선택하거나, A* 알고리즘에서 가장 유망한 경로를 탐색하는 경우에 매우 유용합니다. 전통적인 방법과의 비교를 해보면, 기존에는 요소를 제거한 후 전체를 다시 정렬해야 했다면(O(n log n)), 이제는 Heapify Down으로 O(log n)만에 힙 속성을 복구할 수 있습니다.
Heapify Down의 핵심 특징은 세 가지입니다. 첫째, 두 자식 중 더 작은(최소 힙의 경우) 자식과 교환하여 힙 속성을 보장합니다.
둘째, 마지막 요소를 루트로 옮김으로써 완전 이진 트리 구조를 유지합니다. 셋째, 트리 높이만큼만 비교하므로 O(log n) 시간에 완료됩니다.
이러한 특징들이 중요한 이유는 삭제 연산의 효율성과 정확성을 동시에 보장하기 때문입니다.
코드 예제
// MinHeap 클래스에 추가되는 메서드들
class MinHeap {
// ... 이전 코드 ...
// 힙에서 최솟값(루트)를 제거하고 반환
extractMin() {
if (this.heap.length === 0) return null; // 빈 힙 처리
if (this.heap.length === 1) return this.heap.pop(); // 요소가 하나만 있는 경우
const min = this.heap[0]; // 최솟값 저장
this.heap[0] = this.heap.pop(); // 마지막 요소를 루트로 이동
this.heapifyDown(0); // 하향 조정 시작
return min;
}
// 특정 인덱스부터 아래로 내려가며 힙 속성 복구
heapifyDown(index) {
while (true) {
const leftChild = this.getLeftChildIndex(index);
const rightChild = this.getRightChildIndex(index);
let smallest = index; // 현재 노드를 가장 작은 것으로 초기화
// 왼쪽 자식이 더 작으면 갱신
if (leftChild < this.heap.length && this.heap[leftChild] < this.heap[smallest]) {
smallest = leftChild;
}
// 오른쪽 자식이 더 작으면 갱신
if (rightChild < this.heap.length && this.heap[rightChild] < this.heap[smallest]) {
smallest = rightChild;
}
// 현재 노드가 가장 작으면 힙 속성 만족, 종료
if (smallest === index) break;
// 더 작은 자식과 교환하고 계속 아래로
this.swap(index, smallest);
index = smallest;
}
}
}
설명
이것이 하는 일: Heapify Down은 루트에서 시작해서 자식 노드들과 비교하면서 적절한 위치로 이동시켜 힙의 구조적 속성을 복구합니다. 첫 번째로, 루트 제거 과정을 이해해야 합니다.
최솟값은 항상 루트(인덱스 0)에 있으므로 쉽게 찾을 수 있습니다. 하지만 루트를 제거하면 빈자리가 생기고 트리가 두 개로 분리됩니다.
이를 해결하기 위해 마지막 요소를 루트로 옮깁니다. 이렇게 하면 완전 이진 트리 구조는 유지되지만 힙 속성은 위배될 수 있습니다.
그 다음으로, 하향 이동 과정이 실행됩니다. 루트로 옮겨진 요소는 대부분 큰 값이므로 아래로 내려가야 합니다.
현재 노드와 두 자식을 비교해서 세 개 중 가장 작은 값을 찾습니다. 만약 자식 중 하나가 더 작다면 그 자식과 교환합니다.
교환 후에는 그 자식의 위치로 내려가서 다시 그 자식들과 비교하는 과정을 반복합니다. 세 번째로, 중요한 선택 로직이 있습니다.
자식이 둘 다 있을 때는 더 작은 자식과 교환해야 합니다. 만약 더 큰 자식과 교환하면 힙 속성이 여전히 위배될 수 있기 때문입니다.
예를 들어, 부모가 10이고 왼쪽 자식이 3, 오른쪽 자식이 5라면 반드시 3과 교환해야 합니다. 5와 교환하면 3이 여전히 부모보다 작아서 문제가 됩니다.
네 번째로, 종료 조건을 파악해야 합니다. 세 가지 경우에 Heapify Down이 멈춥니다.
첫째, 현재 노드가 두 자식보다 작거나 같으면 힙 속성이 만족되므로 중단합니다. 둘째, 리프 노드에 도달하면 더 이상 내려갈 곳이 없으므로 종료합니다.
셋째, 자식이 하나만 있고 그 자식보다 현재 노드가 작으면 종료합니다. 여러분이 이 알고리즘을 사용하면 힙에서 최솟값을 효율적으로 추출하면서도 다음 최솟값에 바로 접근할 수 있습니다.
실무에서는 힙 정렬 구현, 우선순위 큐에서 작업 처리, Top K 문제 해결, 이벤트 시뮬레이션 등에 활용됩니다. 특히 반복적으로 최솟값을 추출해야 하는 시스템에서 Heapify Down의 성능이 전체 처리량을 결정합니다.
실전 팁
💡 자식 인덱스가 배열 범위를 벗어나는지 항상 체크하세요. 리프 노드 근처에서는 자식이 없거나 하나만 있을 수 있습니다.
💡 마지막 요소를 루트로 옮길 때 pop()을 사용하면 자동으로 배열 크기가 줄어듭니다. 별도의 크기 관리가 필요 없습니다.
💡 최대 힙과 최소 힙의 차이는 비교 연산자만 바꾸면 됩니다. '<'를 '>'로 바꾸는 것만으로 최대 힙 구현이 가능합니다.
💡 extractMin을 여러 번 호출하면 정렬된 순서로 요소를 얻을 수 있습니다. 이것이 바로 힙 정렬의 원리입니다.
💡 성능 최적화를 위해 불필요한 교환을 줄이세요. 값만 저장해두고 최종 위치가 정해지면 한 번만 할당하는 방식도 가능합니다.
4. Build Heap (힙 구축) - 배열을 O(n)에 힙으로 변환
시작하며
여러분이 이미 존재하는 배열을 힙으로 만들어야 할 때 이런 고민을 하게 됩니다. "배열의 각 요소를 하나씩 insert로 추가하면 O(n log n)이 걸리는데, 더 빠른 방법은 없을까?" 대량의 데이터를 한 번에 힙으로 변환해야 하는 상황에서 이 차이는 성능에 큰 영향을 미칩니다.
이런 문제는 실제 개발 현장에서 자주 발생합니다. 예를 들어, 데이터베이스에서 수백만 개의 레코드를 읽어와서 우선순위 큐로 만들거나, 로그 파일에서 이벤트들을 읽어서 시간순으로 처리하거나, 초기 데이터셋으로 힙을 구축해야 할 때 말이죠.
하나씩 삽입하면 시간이 너무 오래 걸립니다. 바로 이럴 때 필요한 것이 Build Heap(힙 구축) 알고리즘입니다.
배열의 절반 지점부터 시작해서 각 노드에 Heapify Down을 적용하는 방식으로 놀랍게도 O(n) 시간에 힙을 만들 수 있습니다.
개요
간단히 말해서, Build Heap은 무작위 배열을 받아서 마지막 비리프 노드부터 루트까지 역순으로 Heapify Down을 수행하여 전체를 힙으로 만드는 과정입니다. 왜 이 알고리즘이 필요한지 실무 관점에서 설명하면, 초기 데이터를 효율적으로 힙으로 변환하기 위해서입니다.
예를 들어, 대용량 데이터 분석에서 Top K 요소를 찾거나, 머신러닝 파이프라인에서 배치 데이터를 우선순위 큐로 처리하거나, 게임 서버 시작 시 플레이어 순위를 초기화하는 경우에 매우 유용합니다. 전통적인 방법과의 비교를 해보면, 기존에는 각 요소를 하나씩 insert로 추가했다면(O(n log n)), 이제는 Build Heap으로 O(n)에 완성할 수 있습니다.
이는 데이터 크기가 클수록 엄청난 성능 향상입니다. Build Heap의 핵심 특징은 세 가지입니다.
첫째, 리프 노드는 이미 힙이므로 처리할 필요가 없어 절반만 작업하면 됩니다. 둘째, 아래에서 위로 진행하므로 하위 트리가 먼저 힙이 되어 Heapify Down이 정확히 작동합니다.
셋째, 수학적으로 증명된 O(n) 시간 복잡도를 가집니다. 이러한 특징들이 중요한 이유는 대량 데이터를 실시간에 가깝게 처리할 수 있게 해주기 때문입니다.
코드 예제
// MinHeap 클래스에 추가되는 메서드
class MinHeap {
// ... 이전 코드 ...
// 배열을 받아서 힙으로 변환하는 생성자
constructor(array = []) {
this.heap = array;
this.buildHeap(); // 배열을 힙으로 구축
}
// 배열 전체를 힙으로 변환
buildHeap() {
// 마지막 비리프 노드의 인덱스 계산
const startIndex = Math.floor(this.heap.length / 2) - 1;
// 뒤에서부터 앞으로 각 노드에 heapifyDown 적용
for (let i = startIndex; i >= 0; i--) {
this.heapifyDown(i);
}
}
// 배열의 크기 반환
size() {
return this.heap.length;
}
// 최솟값 확인 (제거하지 않음)
peek() {
return this.heap.length > 0 ? this.heap[0] : null;
}
}
// 사용 예시
const arr = [9, 5, 6, 2, 3, 7, 1, 4, 8];
const heap = new MinHeap(arr);
console.log(heap.heap); // 힙으로 변환된 배열 출력
설명
이것이 하는 일: Build Heap은 임의의 배열을 받아서 힙 속성을 만족하는 완전 이진 트리로 재구성합니다. 첫 번째로, 시작 위치를 이해해야 합니다.
완전 이진 트리에서 인덱스 n/2부터 n-1까지는 모두 리프 노드입니다. 리프 노드는 자식이 없으므로 이미 힙 속성을 만족합니다.
따라서 마지막 비리프 노드인 floor(n/2) - 1부터 시작하면 됩니다. 이렇게 하는 이유는 불필요한 작업을 절반 줄여 효율성을 높이기 위해서입니다.
그 다음으로, 역순 진행의 중요성을 파악해야 합니다. 배열의 뒤에서 앞으로 진행하면서 각 노드에 Heapify Down을 적용합니다.
이렇게 하면 현재 노드의 자식 서브트리는 이미 힙으로 정리된 상태이므로 Heapify Down이 올바르게 작동합니다. 만약 앞에서 뒤로 진행하면 자식 트리가 아직 힙이 아니어서 제대로 동작하지 않습니다.
세 번째로, 시간 복잡도가 왜 O(n)인지 이해하는 것이 중요합니다. 직관적으로는 n/2개 노드에 O(log n) 작업을 하니까 O(n log n)처럼 보이지만, 실제로는 다릅니다.
대부분의 노드는 트리 아래쪽에 있고, 아래쪽 노드는 Heapify Down에서 짧은 거리만 이동합니다. 수학적으로 계산하면 총 비교 횟수가 O(n)에 수렴합니다.
네 번째로, 구체적인 예시를 보겠습니다. [9, 5, 6, 2, 3, 7, 1, 4, 8] 배열이 있다면, 마지막 비리프 노드는 인덱스 3(값 2)입니다.
인덱스 3, 2, 1, 0 순서로 heapifyDown을 적용합니다. 각 단계마다 하위 트리가 힙으로 정리되고, 최종적으로 전체가 힙이 됩니다.
여러분이 이 알고리즘을 사용하면 대량의 데이터를 빠르게 힙으로 변환할 수 있습니다. 실무에서는 힙 정렬의 첫 단계, 대용량 데이터의 Top K 문제, 스트리밍 데이터의 초기 버퍼 구축, 게임 리더보드 초기화 등에 활용됩니다.
특히 초기 설정 시간이 중요한 시스템에서 O(n) 구축이 O(n log n) 대비 큰 차이를 만듭니다. 데이터 크기가 100만 개라면 log n이 약 20이므로, 구축 시간이 20배 가까이 차이 날 수 있습니다.
실전 팁
💡 배열을 복사하지 말고 그 자리에서(in-place) 힙으로 만드세요. 추가 메모리 O(1)만 사용하여 공간 효율적입니다.
💡 Build Heap 후에는 항상 peek()으로 루트를 확인해서 힙이 제대로 구축되었는지 검증하세요. 루트가 최솟값이어야 합니다.
💡 힙 정렬을 구현할 때는 Build Heap을 먼저 호출한 후 반복적으로 extractMin을 하면 됩니다. 이 조합이 O(n log n) 정렬을 만듭니다.
💡 대규모 데이터셋에서는 Build Heap을 병렬화할 수 있습니다. 각 서브트리를 독립적으로 힙으로 만든 후 병합하는 방식입니다.
💡 원본 배열을 보존해야 한다면 배열을 복사한 후 Build Heap을 호출하세요. slice()나 spread 연산자로 얕은 복사를 하면 됩니다.
5. 힙 정렬 (Heap Sort) - 정렬 알고리즘으로 활용
시작하며
여러분이 데이터를 정렬해야 할 때 "어떤 알고리즘을 선택해야 할까?" 고민합니다. 퀵 정렬은 빠르지만 최악의 경우 O(n²)이고, 머지 정렬은 안정적이지만 O(n)의 추가 메모리가 필요합니다.
제자리 정렬이면서 최악의 경우에도 O(n log n)을 보장하는 방법은 없을까요? 이런 문제는 메모리가 제한된 임베디드 시스템이나, 대용량 데이터를 정렬해야 하는 상황에서 중요합니다.
예를 들어, 외부 정렬이 필요한 데이터베이스 시스템이나, 실시간 시스템에서 최악의 경우 성능을 보장해야 할 때 말이죠. 불안정한 성능은 치명적일 수 있습니다.
바로 이럴 때 필요한 것이 힙 정렬(Heap Sort)입니다. 힙을 이용해서 제자리에서(in-place) 정렬하면서도 모든 경우에 O(n log n) 시간 복잡도를 보장합니다.
개요
간단히 말해서, 힙 정렬은 배열을 힙으로 만든 후 반복적으로 최댓값(또는 최솟값)을 추출하여 정렬된 배열을 만드는 비교 기반 정렬 알고리즘입니다. 왜 이 알고리즘이 필요한지 실무 관점에서 설명하면, 안정적인 성능과 메모리 효율성이 모두 중요한 상황에서 최적의 선택이 되기 때문입니다.
예를 들어, 임베디드 시스템의 센서 데이터 정렬, 실시간 분석 시스템의 로그 처리, 메모리 제약이 있는 모바일 앱의 데이터 정렬 같은 경우에 매우 유용합니다. 전통적인 방법과의 비교를 해보면, 기존에는 퀵 정렬의 불안정한 성능이나 머지 정렬의 메모리 오버헤드를 감수해야 했다면, 이제는 힙 정렬로 두 가지 문제를 모두 해결할 수 있습니다.
힙 정렬의 핵심 특징은 네 가지입니다. 첫째, 최악의 경우에도 O(n log n)을 보장합니다.
둘째, 추가 메모리가 O(1)만 필요한 제자리 정렬입니다. 셋째, 불안정 정렬이므로 같은 값의 상대적 순서가 바뀔 수 있습니다.
넷째, 캐시 지역성이 낮아서 실제 성능은 퀵 정렬보다 느릴 수 있습니다. 이러한 특징들을 이해하면 상황에 맞는 정렬 알고리즘을 선택할 수 있습니다.
코드 예제
// 힙 정렬 구현
function heapSort(arr) {
const n = arr.length;
// 1단계: 최대 힙 구축 (배열을 힙으로 변환)
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapifyForSort(arr, n, i);
}
// 2단계: 하나씩 요소를 추출하여 정렬
for (let i = n - 1; i > 0; i--) {
// 현재 루트(최댓값)를 배열 끝으로 이동
[arr[0], arr[i]] = [arr[i], arr[0]];
// 힙 크기를 줄이고 루트에 대해 heapify 수행
heapifyForSort(arr, i, 0);
}
return arr;
}
// 최대 힙을 위한 heapify (특정 범위에서만 작동)
function heapifyForSort(arr, heapSize, index) {
let largest = index;
const left = 2 * index + 1;
const right = 2 * index + 2;
// 왼쪽 자식이 더 크면 갱신
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
// 오른쪽 자식이 더 크면 갱신
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
// 자식이 더 크면 교환하고 재귀적으로 heapify
if (largest !== index) {
[arr[index], arr[largest]] = [arr[largest], arr[index]];
heapifyForSort(arr, heapSize, largest);
}
}
// 사용 예시
const data = [12, 11, 13, 5, 6, 7];
console.log("정렬 전:", data);
heapSort(data);
console.log("정렬 후:", data);
설명
이것이 하는 일: 힙 정렬은 힙 자료구조의 속성을 이용해서 배열을 오름차순(또는 내림차순)으로 정렬합니다. 첫 번째로, 최대 힙 구축 단계를 이해해야 합니다.
오름차순 정렬을 위해서는 최대 힙을 사용합니다(역설적이지만 최댓값을 먼저 뒤로 보내기 위해). Build Heap 알고리즘으로 배열 전체를 최대 힙으로 만듭니다.
이 단계는 O(n) 시간이 걸리며, 완료되면 루트에 배열의 최댓값이 위치합니다. 그 다음으로, 반복적 추출 과정이 실행됩니다.
루트(최댓값)를 배열의 마지막 위치와 교환합니다. 그러면 최댓값이 올바른 위치에 고정됩니다.
이제 힙의 크기를 하나 줄이고(마지막 요소 제외), 새로운 루트에 대해 Heapify Down을 수행합니다. 이 과정을 배열이 정렬될 때까지 반복합니다.
세 번째로, 제자리 정렬의 원리를 파악해야 합니다. 교환을 통해 정렬된 부분을 배열의 뒤쪽에 쌓아갑니다.
힙의 유효 범위는 점점 줄어들고, 정렬된 영역은 점점 늘어납니다. 추가 배열이 필요 없이 원본 배열 내에서 모든 작업이 이루어지므로 메모리 효율적입니다.
네 번째로, 시간 복잡도를 분석하면 Build Heap이 O(n), 그리고 n번의 추출마다 O(log n)의 Heapify Down이 필요하므로 총 O(n log n)입니다. 이는 최선, 평균, 최악의 경우 모두 동일합니다.
퀵 정렬의 최악 O(n²)과 달리 안정적인 성능을 보장합니다. 마지막으로, 실무에서의 고려사항입니다.
힙 정렬은 이론적으로 훌륭하지만, 캐시 미스가 많아서 실제 성능은 퀵 정렬보다 느린 경우가 많습니다. 하지만 최악의 경우 성능이 중요하거나, 메모리가 제한적이거나, 안정성보다 성능 보장이 중요한 상황에서는 최고의 선택입니다.
여러분이 이 알고리즘을 사용하면 예측 가능한 성능으로 데이터를 정렬할 수 있습니다. 실무에서는 시스템 프로그래밍, 임베디드 시스템, 실시간 시스템, 커널 수준의 정렬 등에 활용됩니다.
특히 메모리 할당이 불가능하거나 최악의 경우 성능을 보장해야 하는 환경에서 힙 정렬의 가치가 빛납니다.
실전 팁
💡 오름차순 정렬에는 최대 힙을, 내림차순 정렬에는 최소 힙을 사용하세요. 반대로 하면 여러 번 교환해야 해서 비효율적입니다.
💡 작은 배열(n < 10)에서는 삽입 정렬이 더 빠를 수 있습니다. 하이브리드 접근법으로 크기에 따라 알고리즘을 선택하세요.
💡 안정 정렬이 필요하다면 힙 정렬 대신 머지 정렬을 사용하세요. 힙 정렬은 같은 값의 순서를 보장하지 않습니다.
💡 힙 정렬을 병렬화하기는 어렵습니다. 병렬 처리가 필요하다면 머지 정렬이나 퀵 정렬이 더 적합합니다.
💡 성능 비교를 위해 실제 데이터로 벤치마크하세요. 데이터 분포와 크기에 따라 최적의 알고리즘이 다를 수 있습니다.
6. 우선순위 큐 구현 - 힙의 실전 활용
시작하며
여러분이 작업 스케줄링 시스템을 개발할 때 이런 요구사항을 받습니다. "작업을 추가하고, 가장 중요한 작업을 빠르게 가져오고, 작업의 우선순위를 변경할 수 있어야 합니다." 일반 배열이나 큐로는 이 모든 연산을 효율적으로 처리할 수 없습니다.
이런 문제는 실제 소프트웨어 개발에서 매우 흔합니다. 예를 들어, 운영체제의 프로세스 스케줄링, 네트워크 라우터의 패킷 처리, 게임의 이벤트 시스템, 병원의 응급실 관리 시스템 등에서 우선순위 기반 처리가 필수적입니다.
단순한 FIFO 큐로는 중요도를 반영할 수 없습니다. 바로 이럴 때 필요한 것이 우선순위 큐(Priority Queue)입니다.
힙을 기반으로 구현하면 삽입 O(log n), 최고 우선순위 조회 O(1), 추출 O(log n)의 효율적인 연산이 가능합니다.
개요
간단히 말해서, 우선순위 큐는 각 요소가 우선순위를 가지며, 항상 가장 높은 우선순위의 요소가 먼저 처리되는 추상 자료구조입니다. 왜 이 자료구조가 필요한지 실무 관점에서 설명하면, 중요도에 따라 작업을 처리하는 모든 시스템의 핵심이기 때문입니다.
예를 들어, 이메일 서버에서 중요 메일을 먼저 전송하거나, 비디오 스트리밍에서 프레임 우선순위를 관리하거나, AI 탐색 알고리즘에서 유망한 경로를 먼저 탐색하는 경우에 매우 유용합니다. 전통적인 방법과의 비교를 해보면, 기존에는 정렬된 배열(삽입 O(n), 추출 O(1)) 또는 비정렬 배열(삽입 O(1), 추출 O(n))을 사용했다면, 이제는 힙 기반 우선순위 큐로 모든 연산을 O(log n) 이하로 만들 수 있습니다.
우선순위 큐의 핵심 특징은 세 가지입니다. 첫째, 일반 큐와 달리 FIFO가 아니라 우선순위 기반입니다.
둘째, 힙으로 구현하면 시간과 공간 효율성이 최적입니다. 셋째, 비교 함수를 커스터마이징하여 다양한 우선순위 정책을 구현할 수 있습니다.
이러한 특징들이 중요한 이유는 실무의 복잡한 요구사항을 효율적으로 처리할 수 있게 해주기 때문입니다.
코드 예제
// 우선순위 큐 클래스 (최소 힙 기반)
class PriorityQueue {
constructor(compareFn = (a, b) => a - b) {
this.heap = [];
this.compare = compareFn; // 커스텀 비교 함수
}
// 요소 추가
enqueue(value) {
this.heap.push(value);
this.heapifyUp(this.heap.length - 1);
}
// 최고 우선순위 요소 제거 및 반환
dequeue() {
if (this.isEmpty()) return null;
if (this.heap.length === 1) return this.heap.pop();
const top = this.heap[0];
this.heap[0] = this.heap.pop();
this.heapifyDown(0);
return top;
}
// 최고 우선순위 요소 확인 (제거하지 않음)
peek() {
return this.isEmpty() ? null : this.heap[0];
}
// 큐가 비어있는지 확인
isEmpty() {
return this.heap.length === 0;
}
// 큐의 크기 반환
size() {
return this.heap.length;
}
// Heapify Up 구현
heapifyUp(index) {
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.compare(this.heap[index], this.heap[parentIndex]) >= 0) break;
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
// Heapify Down 구현
heapifyDown(index) {
while (true) {
const left = 2 * index + 1;
const right = 2 * index + 2;
let smallest = index;
if (left < this.heap.length && this.compare(this.heap[left], this.heap[smallest]) < 0) {
smallest = left;
}
if (right < this.heap.length && this.compare(this.heap[right], this.heap[smallest]) < 0) {
smallest = right;
}
if (smallest === index) break;
[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
index = smallest;
}
}
}
// 사용 예시: 작업 스케줄러
const taskQueue = new PriorityQueue((a, b) => a.priority - b.priority);
taskQueue.enqueue({ name: "이메일 전송", priority: 3 });
taskQueue.enqueue({ name: "결제 처리", priority: 1 });
taskQueue.enqueue({ name: "로그 저장", priority: 5 });
console.log(taskQueue.dequeue()); // { name: "결제 처리", priority: 1 }
설명
이것이 하는 일: 우선순위 큐는 일반 큐의 FIFO 순서 대신 각 요소의 우선순위에 따라 처리 순서를 결정하는 추상 자료구조입니다. 첫 번째로, 추상 자료구조로서의 의미를 이해해야 합니다.
우선순위 큐는 인터페이스(enqueue, dequeue, peek)를 정의하지만 구현 방법은 자유롭습니다. 배열, 연결 리스트, 힙 등으로 구현할 수 있지만, 힙이 가장 효율적입니다.
이는 스택이나 큐처럼 논리적 개념이며, 실제 사용 방식에 집중합니다. 그 다음으로, 커스텀 비교 함수의 중요성을 파악해야 합니다.
단순한 숫자 비교뿐 아니라 객체의 특정 속성, 복잡한 비교 로직, 여러 기준의 조합 등을 구현할 수 있습니다. 예를 들어, 우선순위가 같으면 등록 시간으로 비교하거나, 특정 조건에 따라 동적으로 우선순위를 계산할 수 있습니다.
이 유연성이 실무에서 매우 중요합니다. 세 번째로, 실전 활용 패턴을 알아야 합니다.
Dijkstra 알고리즘에서는 현재까지의 최단 거리를 우선순위로 사용합니다. A* 알고리즘에서는 f(n) = g(n) + h(n) 값을 우선순위로 합니다.
허프만 코딩에서는 빈도수가 낮은 것부터 처리합니다. 이벤트 드리븐 시뮬레이션에서는 발생 시간을 우선순위로 사용합니다.
네 번째로, 우선순위 변경 문제를 다뤄야 합니다. 기본 힙은 요소의 우선순위 변경을 지원하지 않습니다.
변경이 필요하면 해당 요소를 찾아서(O(n)) 우선순위를 바꾸고 heapify해야 합니다. 더 효율적으로 하려면 인덱스 맵을 추가로 유지해서 O(log n)에 변경할 수 있습니다.
실무에서는 요구사항에 따라 선택합니다. 여러분이 이 자료구조를 사용하면 중요도에 따른 처리, 실시간 시스템, 이벤트 드리븐 아키텍처 등을 효율적으로 구현할 수 있습니다.
실무에서는 작업 큐, CPU 스케줄링, 네트워크 라우팅, 그래프 알고리즘, 시뮬레이션, 이벤트 루프 등 거의 모든 곳에서 우선순위 큐가 사용됩니다. JavaScript에서는 직접 구현해야 하지만, 한 번 만들어두면 다양한 프로젝트에서 재사용할 수 있는 핵심 유틸리티입니다.
실전 팁
💡 비교 함수는 일관성이 있어야 합니다. a < b이고 b < c이면 a < c여야 하며, 이를 위반하면 힙이 깨집니다.
💡 같은 우선순위를 가진 요소들의 순서가 중요하다면 타임스탬프나 시퀀스 번호를 추가하세요. 힙은 불안정 정렬이므로 보조 키가 필요합니다.
💡 대용량 데이터에서는 우선순위 큐를 여러 개로 분할하세요. 예를 들어, 우선순위 범위별로 여러 큐를 두고 라운드 로빈으로 처리하는 방식입니다.
💡 메모리 제약이 있다면 고정 크기 우선순위 큐를 구현하세요. 크기가 초과되면 가장 낮은 우선순위 요소를 자동으로 제거합니다.
💡 성능 모니터링을 위해 큐의 크기와 대기 시간을 추적하세요. 큐가 계속 증가하면 처리 속도가 생성 속도를 따라가지 못하는 것입니다.
7. Top K 문제 해결 - 힙을 활용한 효율적인 선택
시작하며
여러분이 대용량 데이터에서 상위 K개의 요소를 찾아야 할 때 이런 고민을 하게 됩니다. "전체를 정렬하면 O(n log n)인데, K개만 필요한데 전체를 정렬해야 할까?" 특히 K가 n보다 훨씬 작을 때 이런 비효율이 아깝게 느껴집니다.
이런 문제는 실제 데이터 분석과 추천 시스템에서 자주 발생합니다. 예를 들어, 수백만 개의 상품 중 인기 상위 10개를 찾거나, 수백만 명의 유저 중 점수 상위 100명을 찾거나, 로그 파일에서 가장 빈번한 에러 10개를 찾는 경우 말이죠.
전체 정렬은 불필요하게 많은 계산을 합니다. 바로 이럴 때 필요한 것이 힙을 이용한 Top K 알고리즘입니다.
크기 K의 힙을 유지하면서 O(n log K) 시간에 상위 K개를 찾을 수 있으며, K가 작을수록 전체 정렬보다 훨씬 효율적입니다.
개요
간단히 말해서, Top K 문제는 n개의 요소 중에서 가장 큰(또는 작은) K개의 요소를 찾는 선택 문제이며, 힙을 사용하면 효율적으로 해결할 수 있습니다. 왜 이 알고리즘이 필요한지 실무 관점에서 설명하면, 빅데이터 환경에서 전체 데이터를 정렬하지 않고도 필요한 정보를 빠르게 추출하기 위해서입니다.
예를 들어, 실시간 트렌딩 토픽 추출, 추천 시스템의 상위 추천 아이템 선정, 이상 탐지에서 가장 의심스러운 케이스 선별, 네트워크 트래픽 분석에서 최다 요청 IP 파악 등의 경우에 매우 유용합니다. 전통적인 방법과의 비교를 해보면, 기존에는 전체 정렬(O(n log n))이나 선택 정렬(O(n*K))을 사용했다면, 이제는 힙으로 O(n log K)에 해결할 수 있습니다.
n=1,000,000이고 K=10이라면 log K ≈ 3.3, log n ≈ 20이므로 약 6배 빠릅니다. Top K 알고리즘의 핵심 특징은 세 가지입니다.
첫째, 최대 K개를 찾을 때는 최소 힙을, 최소 K개를 찾을 때는 최대 힙을 사용합니다(역설적이지만 이유가 있습니다). 둘째, 스트리밍 데이터에도 적용 가능하여 전체 데이터를 메모리에 올리지 않아도 됩니다.
셋째, 공간 복잡도가 O(K)로 제한되어 메모리 효율적입니다. 이러한 특징들이 중요한 이유는 대규모 데이터 처리와 실시간 분석을 가능하게 하기 때문입니다.
코드 예제
// Top K 최댓값 찾기 (최소 힙 사용)
function findTopK(arr, k) {
// 크기 K의 최소 힙 생성
const minHeap = new PriorityQueue((a, b) => a - b);
for (let i = 0; i < arr.length; i++) {
if (minHeap.size() < k) {
// 힙이 K개 미만이면 무조건 추가
minHeap.enqueue(arr[i]);
} else if (arr[i] > minHeap.peek()) {
// 현재 요소가 힙의 최솟값보다 크면 교체
minHeap.dequeue(); // 가장 작은 것 제거
minHeap.enqueue(arr[i]); // 현재 요소 추가
}
}
// 힙의 모든 요소를 배열로 반환
const result = [];
while (!minHeap.isEmpty()) {
result.push(minHeap.dequeue());
}
return result.reverse(); // 큰 순서로 정렬
}
// 스트리밍 Top K 클래스
class StreamingTopK {
constructor(k) {
this.k = k;
this.minHeap = new PriorityQueue((a, b) => a - b);
}
// 새로운 값 추가
add(value) {
if (this.minHeap.size() < this.k) {
this.minHeap.enqueue(value);
} else if (value > this.minHeap.peek()) {
this.minHeap.dequeue();
this.minHeap.enqueue(value);
}
}
// 현재 Top K 반환
getTopK() {
return [...this.minHeap.heap].sort((a, b) => b - a);
}
}
// 사용 예시
const data = [5, 12, 3, 8, 15, 7, 20, 1, 9];
console.log("Top 3:", findTopK(data, 3)); // [20, 15, 12]
설명
이것이 하는 일: Top K 알고리즘은 전체 데이터를 정렬하지 않고도 가장 큰(또는 작은) K개의 요소를 효율적으로 선택합니다. 첫 번째로, 왜 최소 힙을 사용하는지 이해해야 합니다.
최댓값 K개를 찾을 때 최소 힙을 쓰는 이유는 힙의 루트가 K개 중 가장 작은 값이기 때문입니다. 새로운 요소가 이 최솟값보다 크면 그 요소는 Top K에 포함되어야 하므로 최솟값을 제거하고 새 요소를 추가합니다.
반대로 새 요소가 최솟값보다 작으면 Top K에 들어갈 수 없으므로 무시합니다. 이 메커니즘이 알고리즘의 핵심입니다.
그 다음으로, 알고리즘의 진행 과정을 살펴봅시다. 처음 K개 요소는 무조건 힙에 추가합니다.
K+1번째 요소부터는 힙의 루트와 비교해서 크면 교체, 작으면 무시합니다. 모든 요소를 처리하고 나면 힙에 남은 K개가 바로 Top K입니다.
각 요소마다 최대 O(log K)의 연산이므로 총 O(n log K) 시간이 걸립니다. 세 번째로, 스트리밍 시나리오를 이해해야 합니다.
전체 데이터를 한 번에 받지 못하고 실시간으로 들어오는 경우에도 동일한 방식이 작동합니다. 힙은 항상 현재까지의 Top K를 유지하므로, 언제든지 최신 Top K를 조회할 수 있습니다.
메모리는 항상 O(K)만 사용하므로 무한 스트림도 처리 가능합니다. 트위터의 실시간 트렌딩이나 주식 시장의 가장 활발한 종목 추적 같은 곳에 활용됩니다.
네 번째로, 변형 문제들을 알아봅시다. Top K 최빈값(frequency)을 찾으려면 먼저 각 요소의 빈도를 세고(HashMap), 그 빈도를 기준으로 Top K를 찾으면 됩니다.
Top K 가장 가까운 값(closest to target)을 찾으려면 목표값과의 거리를 우선순위로 사용합니다. K번째 큰 값을 찾으려면 크기 K의 최소 힙을 유지하고 루트를 반환하면 됩니다.
여러분이 이 알고리즘을 사용하면 대용량 데이터에서 효율적으로 상위 요소를 추출할 수 있습니다. 실무에서는 추천 시스템의 Top N 추천, 리더보드와 랭킹 시스템, 로그 분석의 상위 에러, 검색 엔진의 상위 결과, 광고 시스템의 최고 입찰자 선정 등에 활용됩니다.
특히 빅데이터 환경에서 Hadoop이나 Spark 같은 분산 시스템과 결합하면 더욱 강력합니다. 각 노드에서 로컬 Top K를 찾고, 이를 병합해서 글로벌 Top K를 구하는 방식입니다.
실전 팁
💡 K가 n/2보다 크면 전체 정렬이 더 효율적일 수 있습니다. K의 크기에 따라 알고리즘을 선택하세요.
💡 최소 K개를 찾을 때는 최대 힙을 사용해야 합니다. 최댓값과 정반대 논리로 작동합니다.
💡 객체 배열에서 Top K를 찾을 때는 비교 함수를 정확히 정의하세요. 예: (a, b) => a.score - b.score
💡 정확한 Top K가 아니라 대략적인 Top K로 충분하다면 Count-Min Sketch 같은 근사 알고리즘을 사용해 메모리를 더 절약할 수 있습니다.
💡 여러 기준으로 Top K를 찾아야 한다면(예: 점수가 같으면 시간 순) 비교 함수에 여러 조건을 넣거나 복합 키를 사용하세요.
8. 중간값 찾기 (Median Finding) - 두 개의 힙 활용
시작하며
여러분이 스트리밍 데이터의 중간값을 실시간으로 추적해야 할 때 이런 문제에 직면합니다. "데이터가 계속 추가되는데 매번 정렬해서 중간값을 찾으면 너무 느린데, 더 빠른 방법은 없을까?" 중간값은 정렬된 데이터의 정중앙이므로 전체 정렬이 필요해 보입니다.
이런 문제는 실시간 통계 분석과 모니터링 시스템에서 중요합니다. 예를 들어, 웹 서버의 응답 시간 중간값을 실시간으로 추적하거나, 주식 가격의 중간값 추이를 모니터링하거나, 센서 데이터의 중간값으로 이상치를 필터링하는 경우 말이죠.
중간값은 평균과 달리 이상치에 강건하므로 많이 사용됩니다. 바로 이럴 때 필요한 것이 두 개의 힙을 사용한 중간값 추적 알고리즘입니다.
최대 힙과 최소 힙을 조합하면 삽입 O(log n), 중간값 조회 O(1)로 효율적으로 중간값을 유지할 수 있습니다.
개요
간단히 말해서, 중간값 찾기 알고리즘은 최대 힙(작은 쪽 절반)과 최소 힙(큰 쪽 절반)을 사용하여 데이터의 중간값을 효율적으로 추적하는 기법입니다. 왜 이 알고리즘이 필요한지 실무 관점에서 설명하면, 스트리밍 데이터나 동적으로 변하는 데이터셋에서 중간값을 빠르게 계산하기 위해서입니다.
예를 들어, 실시간 성능 모니터링에서 P50(중간값) 지연시간 추적, 금융 데이터의 중간값 기반 이상 거래 탐지, IoT 센서의 중간값 필터링, 실시간 순위 시스템에서 중간 순위 파악 등의 경우에 매우 유용합니다. 전통적인 방법과의 비교를 해보면, 기존에는 매번 정렬해서 중간값을 찾았다면(삽입마다 O(n log n)), 이제는 두 힙 구조로 삽입 O(log n), 조회 O(1)에 중간값을 유지할 수 있습니다.
이 알고리즘의 핵심 특징은 세 가지입니다. 첫째, 데이터를 두 부분으로 나눠서 각각 힙으로 관리합니다.
둘째, 두 힙의 크기 균형을 맞춰서 중간값이 항상 힙의 루트에 있게 합니다. 셋째, 홀수/짝수 개수에 따라 중간값 계산 방식이 다릅니다.
이러한 특징들이 중요한 이유는 중간값을 상수 시간에 조회하면서도 동적 업데이트를 로그 시간에 처리할 수 있기 때문입니다.
코드 예제
// 중간값을 추적하는 MedianFinder 클래스
class MedianFinder {
constructor() {
// 작은 쪽 절반을 관리하는 최대 힙 (큰 값이 위로)
this.maxHeap = new PriorityQueue((a, b) => b - a);
// 큰 쪽 절반을 관리하는 최소 힙 (작은 값이 위로)
this.minHeap = new PriorityQueue((a, b) => a - b);
}
// 새로운 숫자 추가
addNum(num) {
// 1단계: 최대 힙에 먼저 추가
this.maxHeap.enqueue(num);
// 2단계: 최대 힙의 최댓값을 최소 힙으로 이동
// (작은 쪽의 최댓값이 큰 쪽의 최솟값보다 작거나 같도록)
this.minHeap.enqueue(this.maxHeap.dequeue());
// 3단계: 크기 균형 맞추기 (최대 힙이 최소 힙보다 크거나 같도록)
if (this.maxHeap.size() < this.minHeap.size()) {
this.maxHeap.enqueue(this.minHeap.dequeue());
}
}
// 현재 중간값 반환
findMedian() {
if (this.maxHeap.size() > this.minHeap.size()) {
// 홀수 개: 최대 힙의 루트가 중간값
return this.maxHeap.peek();
} else {
// 짝수 개: 두 힙의 루트 평균이 중간값
return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
}
}
}
// 사용 예시
const medianFinder = new MedianFinder();
medianFinder.addNum(1);
medianFinder.addNum(2);
console.log(medianFinder.findMedian()); // 1.5
medianFinder.addNum(3);
console.log(medianFinder.findMedian()); // 2
설명
이것이 하는 일: 이 알고리즘은 데이터를 작은 쪽 절반과 큰 쪽 절반으로 나누고, 각각을 힙으로 관리하여 중간값을 효율적으로 유지합니다. 첫 번째로, 두 힙의 역할을 이해해야 합니다.
최대 힙은 전체 데이터의 작은 쪽 절반을 저장하며, 루트에 이 절반의 최댓값이 옵니다. 최소 힙은 큰 쪽 절반을 저장하며, 루트에 이 절반의 최솟값이 옵니다.
이렇게 하면 두 힙의 루트가 정렬된 배열의 중앙 부근 값들이 되어, 중간값을 쉽게 찾을 수 있습니다. 그 다음으로, 불변 조건(invariant)을 유지하는 방법을 알아야 합니다.
항상 두 가지 조건을 만족해야 합니다. 첫째, 최대 힙의 모든 값은 최소 힙의 모든 값보다 작거나 같아야 합니다.
둘째, 최대 힙의 크기는 최소 힙의 크기와 같거나 1 크게 유지합니다. 이 조건들이 만족되면 중간값은 항상 최대 힙의 루트(홀수 개) 또는 두 루트의 평균(짝수 개)입니다.
세 번째로, 삽입 과정의 세 단계를 파악해야 합니다. 1단계: 새 값을 일단 최대 힙에 넣습니다.
2단계: 최대 힙의 최댓값을 최소 힙으로 옮겨서 첫 번째 불변 조건을 보장합니다. 3단계: 크기 균형이 깨졌다면(최소 힙이 더 크면) 최소 힙의 최솟값을 최대 힙으로 옮깁니다.
이 세 단계가 모든 불변 조건을 자동으로 유지합니다. 네 번째로, 예시를 통해 이해를 돕겠습니다.
[1, 2, 3, 4, 5]를 순서대로 추가한다고 가정합니다. 1 추가 후: maxHeap=[1], minHeap=[], 중간값=1.
2 추가 후: maxHeap=[1], minHeap=[2], 중간값=1.5. 3 추가 후: maxHeap=[2,1], minHeap=[3], 중간값=2.
4 추가 후: maxHeap=[2,1], minHeap=[3,4], 중간값=2.5. 5 추가 후: maxHeap=[3,2,1], minHeap=[4,5], 중간값=3.
각 단계마다 불변 조건이 유지됩니다. 여러분이 이 알고리즘을 사용하면 실시간으로 변하는 데이터의 중간값을 효율적으로 추적할 수 있습니다.
실무에서는 웹 애플리케이션의 응답 시간 P50 모니터링, 데이터베이스 쿼리 지연시간 분석, 네트워크 패킷 지연 추적, 재고 관리의 중간값 기반 예측, 센서 데이터의 노이즈 제거 등에 활용됩니다. 특히 Prometheus나 Grafana 같은 모니터링 도구에서 percentile 계산에 유사한 방식이 사용됩니다.
실전 팁
💡 JavaScript에는 내장 최대 힙이 없으므로 비교 함수를 (b - a)로 설정해서 최소 힙을 최대 힙처럼 동작하게 만드세요.
💡 P25, P75 같은 다른 백분위수도 같은 원리로 구할 수 있습니다. 힙의 크기 비율을 조정하면 됩니다.
💡 삽입뿐 아니라 삭제도 지원하려면 해시맵으로 각 값의 힙 위치를 추적해야 합니다. 구현이 복잡해지므로 필요할 때만 추가하세요.
💡 대용량 데이터에서는 근사 중간값 알고리즘(t-digest, Q-digest)을 고려하세요. 메모리를 대폭 줄이면서도 높은 정확도를 제공합니다.
💡 슬라이딩 윈도우의 중간값을 추적하려면 오래된 값을 제거하는 로직이 필요합니다. 이 경우 힙보다 balanced BST가 더 적합할 수 있습니다.