우리가 앞서 배운 큐(Queue)는 '선착순(FIFO)'이라는 아주 공평한 규칙을 가지고 있었습니다. 먼저 온 사람이 먼저 서비스를 받는 것이죠. 하지만 현실 세계, 특히 생사가 오가는 응급실에서는 이 규칙이 적용되지 않습니다. 감기로 아침 9시에 온 환자보다, 심정지로 10시에 실려 온 환자가 먼저 치료를 받아야 합니다. 이처럼 데이터에 '중요도(Priority)'를 매겨서, 순서와 상관없이 중요한 것부터 먼저 처리하는 자료구조가 바로 우선순위 큐(Priority Queue)이며, 이를 구현하는 가장 효율적인 도구가 힙(Heap)입니다.
1. 힙(Heap)이란 무엇인가?
힙은 완전 이진 트리(Complete Binary Tree) 형태를 띤 자료구조입니다. '무더기'라는 뜻처럼 데이터를 차곡차곡 쌓아 올리되, "대장(최댓값 혹은 최솟값)만은 확실하게 관리한다"는 철학을 가지고 있습니다. 힙은 정렬 상태에 따라 두 가지로 나뉩니다.
- 최대 힙 (Max Heap): 부모 노드가 자식 노드보다 항상 크거나 같습니다. 따라서 루트 노드(꼭대기)에는 데이터 중 가장 큰 값이 위치합니다.
- 최소 힙 (Min Heap): 부모 노드가 자식 노드보다 항상 작거나 같습니다. 따라서 루트 노드에는 데이터 중 가장 작은 값이 위치합니다.
여기서 중요한 점은 '느슨한 정렬'입니다. 이진 탐색 트리(BST)처럼 왼쪽/오른쪽의 대소 관계를 따지지 않고, 오직 위/아래(부모/자식) 관계만 신경 씁니다. 그래서 형제 노드끼리는 누가 큰지 알 수 없습니다.
2. 왜 배열 대신 힙을 쓸까? (성능 비교)
우선순위 큐를 만들 때, 단순히 배열을 정렬해서 쓰면 안 될까요? 가능은 하지만 성능 차이가 심각합니다. 데이터가 $N$개일 때를 비교해 봅시다.
2-1. 배열 사용 시
가장 큰 값을 꺼내려면(Dequeue) 정렬을 해야 합니다. 새로운 데이터가 들어올 때마다 다시 정렬하거나, 적절한 위치를 찾아 삽입하고 뒤의 데이터들을 밀어야 합니다. 이 과정에서 O(N)의 시간이 걸립니다. 데이터가 10만 개라면 10만 번 연산해야 합니다.
2-2. 힙 사용 시
힙은 데이터가 들어오거나 나갈 때, 트리의 높이만큼만 비교하면 됩니다. 트리의 높이는 $\log N$이므로, 시간 복잡도는 O(log N)입니다. 10만 개의 데이터라도 약 17번 정도만 비교하면 자리를 찾습니다. 결과적으로 대용량 데이터를 처리하는 시스템에서는 힙이 압도적으로 빠릅니다.
3. 힙의 동작 원리: 붕괴와 재구조화
힙에서 데이터를 꺼내거나 넣을 때 트리가 무너지는 것을 막기 위해 Heapify라는 과정을 거칩니다.
- 삽입 (Push): 새로운 데이터를 맨 끝에 둡니다. 그리고 부모와 비교해서 자기가 더 세다면(우선순위가 높다면) 부모와 자리를 바꿉니다. 이 과정을 만족할 때까지 위로 올라갑니다.
- 삭제 (Pop): 대장(루트 노드)을 꺼냅니다. 그리고 맨 마지막에 있던 녀석을 루트 자리로 올립니다. 이제 자식들과 비교해서 자기가 더 약하다면 아래로 내려갑니다.
4. 실무 활용 사례
우선순위 큐와 힙은 시스템의 효율성을 높이는 곳에 필수적으로 사용됩니다.
- 작업 스케줄러: 운영체제(OS)는 수많은 프로세스 중 시스템에 중요한 작업(커널 작업 등)에 CPU를 먼저 할당합니다.
- 네트워크 패킷 처리: 라우터는 들어오는 데이터 패킷 중 영상 통화나 게임처럼 실시간성이 중요한 데이터를 먼저 전송합니다.
- 최단 경로 탐색: 내비게이션 알고리즘인 '다익스트라(Dijkstra)'에서 현재 갈 수 있는 가장 가까운 경로를 찾을 때 최소 힙을 사용합니다.
1. 우선순위 큐는 들어온 순서가 아닌 중요도 순으로 데이터를 처리하는 자료구조입니다.
2. 이를 구현하는 힙(Heap)은 최댓값/최솟값을 O(log N) 속도로 빠르게 관리하는 완전 이진 트리입니다.
3. 응급실 시스템, 작업 스케줄링, 최단 경로 탐색 등 순위 결정이 필요한 모든 곳에 쓰입니다.