큐(Queue)가 식당에서 줄을 선 순서대로(First In, First Out) 들어가는 구조라면, 우선순위 큐(Priority Queue)는 응급실처럼 '가장 위급한 환자(가장 우선순위가 높은 데이터)'가 먼저 들어가는 구조입니다.
이러한 우선순위 큐를 가장 빠르고 효율적으로 구현하기 위해 사용하는 마법의 자료구조가 바로 힙(Heap)입니다. 힙은 완전 이진 트리(Complete Binary Tree)의 형태를 가지며, 부모가 자식보다 항상 크거나(Max Heap), 항상 작은(Min Heap) 상태를 유지합니다.
1. 최대 힙(Max Heap) 동작 원리
2. 배열을 통한 힙 구현 (인덱스 공식)
힙은 트리 형태를 띠고 있지만, 실제 메모리 상에서는 배열(Array)로 저장됩니다. 완전 이진 트리의 특성 덕분에 빈 공간 없이 차례대로 배열에 들어맞기 때문입니다.
만약 현재 노드의 인덱스가 i 라면, 부모와 자식 노드의 인덱스는 다음과 같은 마법의 공식으로 즉시 알아낼 수 있습니다.
부모 노드 인덱스 = Math.floor((i - 1) / 2)
왼쪽 자식 인덱스 = 2 * i + 1
오른쪽 자식 인덱스 = 2 * i + 2
💡 실무 지식: 힙은 언제 쓰이나요?
단순히 데이터 전체를 정렬(Sort)해야 한다면 퀵 정렬이나 병합 정렬을 씁니다. 하지만 수많은 데이터 중 "가장 큰 값" 또는 "가장 작은 값" 몇 개만 반복적으로 빠르게 꺼내야 할 때 힙은 빛을 발합니다.
예를 들어 운영체제의 프로세스 스케줄링(가장 중요한 작업 먼저 처리), 다익스트라(Dijkstra) 최단 경로 알고리즘, 슬랙(Slack)이나 카카오톡의 메시지 큐 등에서 핵심적인 엔진 역할을 수행합니다.
// 📂 MaxHeap.js (JavaScript)
// 자바스크립트는 기본적으로 힙이나 우선순위 큐 내장 객체가 없으므로, 배열을 이용해 직접 구현합니다.
class MaxHeap {
constructor() {
this.heap = [];
}
// 부모, 왼쪽 자식, 오른쪽 자식 인덱스 계산 공식
parent(i) { return Math.floor((i - 1) / 2); }
leftChild(i) { return 2 * i + 1; }
rightChild(i) { return 2 * i + 2; }
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
// 🌟 데이터 삽입 (O(log N))
push(value) {
this.heap.push(value);
this.heapifyUp(this.heap.length - 1);
}
// 삽입 후 부모와 비교하며 위로 끌어올림 (Max Heap 성질 복구)
heapifyUp(i) {
while (i > 0 && this.heap[this.parent(i)] < this.heap[i]) {
this.swap(this.parent(i), i);
i = this.parent(i);
}
}
// 🌟 최댓값 추출 (O(log N))
pop() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const max = this.heap[0]; // 루트 노드(최댓값) 저장
this.heap[0] = this.heap.pop(); // 맨 끝 노드를 루트로 올림
this.heapifyDown(0); // 다시 아래로 내리며 정렬
return max;
}
// 루트에서부터 자식과 비교하며 아래로 내려감
heapifyDown(i) {
let maxIndex = i;
const left = this.leftChild(i);
const right = this.rightChild(i);
if (left < this.heap.length && this.heap[left] > this.heap[maxIndex]) {
maxIndex = left;
}
if (right < this.heap.length && this.heap[right] > this.heap[maxIndex]) {
maxIndex = right;
}
if (maxIndex !== i) {
this.swap(i, maxIndex);
this.heapifyDown(maxIndex);
}
}
}
// 실행 예시
const maxHeap = new MaxHeap();
maxHeap.push(15);
maxHeap.push(40);
maxHeap.push(10);
maxHeap.push(50);
console.log("최댓값 추출:", maxHeap.pop()); // 50 출력 (가장 큰 값이 먼저 나옴)
console.log("다음 최댓값 추출:", maxHeap.pop()); // 40 출력
