힙과 우선순위 큐
힙 (Heap)과 우선순위 큐
힙(Heap)은 '완전 이진 트리'에 기반한 자료구조로, 특정 규칙(힙 속성)을 만족하여 최댓값이나 최솟값을 빠르게 찾아내는 데 특화되어 있습니다. 이러한 특징 때문에 힙은 우선순위 큐(Priority Queue)를 구현하는 가장 효율적인 자료구조로 널리 사용됩니다.
🔥 힙 (Heap)의 특징과 종류
- 자료구조 : 완전 이진 트리(Complete Binary Tree)에 기반합니다. 이 때문에 배열을 사용하여 매우 효율적으로 표현할 수 있습니다.
- 힙 속성 (Heap Property) : 부모 노드의 키 값과 자식 노드의 키 값 사이에는 항상 일정한 대소 관계가 성립합니다.
- 종류 (Types)
> * 최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같습니다. (루트 노드가 최댓값) > * 최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 같습니다. (루트 노드가 최솟값)
🛠️ 힙의 주요 연산 (삽입/삭제)
힙의 핵심 연산은 삽입/삭제 후에도 힙 속성을 유지하기 위한 힙 재구성(Heapify) 과정입니다.
- 삽입 (Insertion) - O(log n)
1. 새로운 노드를 힙의 마지막 위치(완전 이진 트리의 마지막)에 추가합니다. 2. 새 노드를 부모 노드와 비교하며 힙 속성을 만족할 때까지 위로(up-heap) 이동시킵니다.
- 삭제 (Deletion) - O(log n)
1. 루트 노드(최댓값 또는 최솟값)를 제거합니다. 2. 힙의 마지막 노드를 루트 위치로 가져옵니다. 3. 새로운 루트를 자식 노드와 비교하며 힙 속성을 만족할 때까지 아래로(down-heap) 이동시킵니다.
🥇 우선순위 큐 (Priority Queue)
- 개념 (Concept) : 들어온 순서와 상관없이, 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다. (FIFO인 큐와 다름)
- 구현 방법
> * '배열/연결 리스트': 삽입 또는 삭제 시 모든 원소를 순회해야 하므로 O(n)의 시간이 걸려 비효율적입니다. > * 힙 (Heap): 삽입과 삭제 모두 O(log n)의 시간 복잡도를 가지므로, 우선순위 큐를 구현하는 데 가장 이상적이고 효율적인 자료구조입니다.
- 활용 사례
> * 운영체제 스케줄링 : 우선순위가 높은 프로세스를 먼저 처리합니다. > * 네트워크 라우팅 : 최단 경로를 찾는 다익스트라(Dijkstra) 알고리즘에서 다음으로 방문할 노드를 선택할 때 사용됩니다. > * 데이터 압축 : 허프만 코딩(Huffman Coding)에서 빈도수가 높은 문자에 높은 우선순위를 부여합니다.
💡 개발자 핵심 Point
- 힙은 '정렬'에도 사용될 수 있습니다 (힙 정렬, Heap Sort). N개의 데이터를 힙에 모두 넣은 뒤, 하나씩 빼내면 정렬된 결과를 얻을 수 있으며, 시간 복잡도는 O(n log n)입니다.
- 가장 크거나 작은 K개의 원소를 찾는 문제, 또는 중간값(Median)을 실시간으로 찾는 문제 등에서 힙을 활용하면 효율적으로 해결할 수 있습니다.
- 대부분의 프로그래밍 언어는 우선순위 큐 라이브러리를 표준으로 제공합니다. (e.g., Java의 `PriorityQueue`, Python의 `heapq` 모듈)
- Java의 `PriorityQueue`는 기본적으로 '최소 힙(Min Heap)'으로 구현되어 있습니다. 최대 힙으로 사용하려면 별도의 Comparator를 제공하거나, 값의 부호를 바꿔서 저장하는 트릭을 사용할 수 있습니다.
