힙(Heap)과 우선순위 큐: 응급실 진료 순서로 이해하는 자료구조

병원의 응급실(ER)에 환자들이 도착하는 상황을 떠올려 보십시오. 접수처에서는 먼저 온 순서대로 줄을 세우는 일반적인 '큐(Queue)' 방식을 사용하지 않습니다. 감기 환자가 먼저 와서 기다리고 있더라도, 피를 흘리는 중증 외상 환자가 들어오는 순간 그 환자가 무조건 진료 순서 1순위로 새치기를 해야 합니다. 이처럼 "들어온 순서와 상관없이, 우선순위가 가장 높은 데이터가 무조건 먼저 나가는" 시스템을 우선순위 큐(Priority Queue)라고 부릅니다. 그리고 이 불공평하지만 합리적인 대기열을 컴퓨터 메모리 상에서 가장 완벽하고 빠르게 구현해 내는 트리 구조가 바로 '힙(Heap)'입니다.

1. 힙(Heap)의 물리적 구조: 완전 이진 트리

힙은 이진 탐색 트리(BST)와 비슷하게 생겼지만 규칙이 완전히 다릅니다. 힙의 유일한 목적은 '가장 큰 값(혹은 가장 작은 값)을 루트(Root) 노드에 띄워 놓는 것'입니다.

• 최대 힙(Max Heap): 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같다는 룰을 가집니다. 따라서 전체 트리에서 가장 큰 값이 자연스럽게 맨 꼭대기(루트)에 위치하게 됩니다. (최소 힙은 그 반대입니다.)
• 왼쪽부터 차곡차곡: 힙은 무조건 트리의 위에서부터 아래로, 왼쪽에서 오른쪽으로 빈틈없이 노드를 채워나가는 완전 이진 트리(Complete Binary Tree)의 형태를 유지합니다. 덕분에 복잡한 포인터 없이 단순한 1차원 '배열'만으로도 트리를 완벽하게 표현할 수 있습니다.

2. 새로운 환자의 개입 (삽입 연산: Up-Heap)

새로운 환자(데이터)가 들어오면, 힙은 일단 트리의 가장 맨 끝(배열의 마지막)에 환자를 배정합니다. 그리고 환자의 위급도(우선순위)를 부모 노드와 비교합니다. 만약 새로 온 환자가 부모보다 더 위급하다면? 둘의 자리를 바꿉니다(Swap). 이 과정을 부모보다 위급도가 낮아지거나, 꼭대기(루트)에 도달할 때까지 위로 거슬러 올라가며 반복합니다. 트리의 높이만큼만 훑으므로 $O(\log N)$ 만에 최적의 위치를 찾아냅니다.

3. VIP의 퇴장과 재정렬 (삭제 연산: Down-Heap)

진료를 마치고 꼭대기에 있던 1순위 환자(최댓값)가 빠져나가면 루트 자리가 텅 빕니다. 힙은 트리의 가장 맨 끝에 있던 꼴찌 데이터를 멱살 잡아 임시로 꼭대기에 앉힙니다. 그 후, 이 가짜 1등을 자신의 두 자식 중 더 우선순위가 높은(더 큰) 자식과 비교하며 아래로 끌어내립니다. 자기보다 작은 자식들만 남을 때까지 계속 밑으로 추락시키는 이 과정 역시 $O(\log N)$ 만에 끝납니다.

[핵심 요약]
1. 우선순위 큐(Priority Queue)는 데이터가 들어온 순서와 무관하게 우선순위가 가장 높은 데이터가 먼저 추출되는 자료구조입니다.
2. 이를 구현하는 가장 최적의 뼈대가 힙(Heap)이며, 부모 노드가 자식 노드보다 항상 우선순위가 높다는 느슨한 정렬 상태를 유지하는 완전 이진 트리입니다.
3. 최댓값/최솟값을 추출하는 데 $O(1)$이 걸리며, 데이터를 삽입하거나 추출 후 트리를 재정렬하는 과정은 $O(\log N)$의 쾌속을 자랑하여 다익스트라(Dijkstra) 알고리즘 등의 심장으로 쓰입니다.