[우선순위 큐와 힙] 효율적인 데이터 처리의 핵심!

우선순위 큐(Priority Queue)와 힙(Heap)은 효율적으로 데이터를 관리하고 처리하는 데 중요한 자료구조입니다. 특히, 우선순위가 중요한 작업 예를들어 작업 스케줄링, 네트워크 패킷 처리에서 자주 사용됩니다. 이번 포스트에서는 우선순위 큐와 힙의 개념, 차이점, 그리고 활용 사례를 알아보겠습니다!

---

1. 우선순위 큐(Priority Queue)란?

1) 정의

• 우선순위 큐는 데이터가 우선순위에 따라 정렬되고 처리되는 큐입니다.

• 일반적인 큐(FIFO)와 달리, 우선순위가 높은 데이터가 먼저 처리됩니다.

2) 동작

• 삽입: 데이터와 우선순위를 함께 저장.

• 삭제: 우선순위가 가장 높은 데이터를 삭제.

3) 특징

• 우선순위 큐는 내부적으로 힙(Heap)을 사용해 구현되는 경우가 많습니다.

• 우선순위가 동일하면 FIFO 방식으로 처리.

2. 힙(Heap)이란?

1) 정의

• 힙은 이진 트리 기반의 완전 이진 트리로, 특정 우선순위 조건을 만족하는 자료구조입니다.

• 최대 힙(Max Heap): 부모 노드가 자식 노드보다 크거나 같음.

• 최소 힙(Min Heap): 부모 노드가 자식 노드보다 작거나 같음.

2) 힙의 특징

• 완전 이진 트리: 마지막 레벨을 제외한 모든 노드가 채워져 있음.

• 힙은 효율적인 삽입과 삭제를 보장.

• 삽입/삭제의 시간 복잡도: O(log N)

3) 힙의 동작

• 삽입: 새로운 데이터를 적절한 위치에 삽입 후, 힙 속성을 유지하기 위해 재배치.

• 삭제: 루트 노드(최댓값 또는 최솟값)를 제거 후, 힙 속성을 유지하기 위해 힙 다운(Heapify) 실행.

3. 우선순위 큐와 힙의 관계

우선순위 큐는 내부적으로 힙을 사용하여 구현되는 경우가 많습니다.

• 최소 힙을 사용하면 우선순위가 낮은 데이터부터 처리.

• 최대 힙을 사용하면 우선순위가 높은 데이터부터 처리.

4. 활용 사례

우선순위 큐의 활용 사례

• 작업 스케줄링

• CPU 작업을 우선순위에 따라 처리.

• 예: 운영 체제의 작업 관리자.

• 네트워크 패킷 처리

• 패킷의 중요도에 따라 전송 순서 결정.

• 다익스트라 알고리즘

• 최단 경로 탐색에서 가중치를 기준으로 우선순위 큐 사용.

• 이벤트 처리 시스템

• 이벤트 우선순위에 따라 처리.

힙의 활용 사례

• 힙 정렬 (Heap Sort)

• 힙을 이용한 효율적인 정렬 알고리즘.

• 우선순위 큐 구현

• 최소 힙 또는 최대 힙을 사용.

• 최소/최대 값 추출

• 데이터 중 최솟값 또는 최댓값을 빠르게 찾음.

• 중앙값 유지 알고리즘

• 최소 힙과 최대 힙을 사용하여 데이터를 동적으로 관리.

5. Python으로 우선순위 큐와 힙 구현

우선순위 큐 구현

Python의 queue.PriorityQueue를 사용하여 간단히 구현 가능합니다.

from queue import PriorityQueue

# 우선순위 큐 생성
pq = PriorityQueue()

# 데이터 삽입 (우선순위, 값)
pq.put((1, "Task 1"))
pq.put((3, "Task 3"))
pq.put((2, "Task 2"))

# 우선순위가 높은 데이터부터 처리
while not pq.empty():
    print(pq.get())  # 출력: (1, 'Task 1') → (2, 'Task 2') → (3, 'Task 3')

힙 구현

Python의 heapq 라이브러리를 사용하여 최소 힙을 구현할 수 있습니다.

import heapq

# 힙 생성
heap = []

# 데이터 삽입
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

# 최솟값 추출
print(heapq.heappop(heap))  # 출력: 1
print(heapq.heappop(heap))  # 출력: 2

우선순위 큐와 힙의 장단점

우선순위 큐의 장점

• 우선순위가 높은 작업을 효율적으로 처리.

• 다양한 자료구조(힙, 배열, 링크드 리스트)로 구현 가능.

우선순위 큐의 단점

• 구현 방식에 따라 성능 차이가 있음.

• 단순 큐보다 복잡한 로직이 필요.