[Python] 알고리즘 개념11 - 우선순위 큐와 힙(Heap)

 

 

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

**우선순위 큐(Priority Queue)**는 값이 들어온 순서와 상관없이 높은 우선순위를 가진 요소가 먼저 나오는 자료구조예요.

 

💡 쉽게 이해하기

• 🏥 응급실 대기열처럼 동작해요!
  • 환자(데이터)의 우선순위에 따라 먼저 치료(처리)돼요.
• 🔢 최소값 또는 최대값을 빠르게 찾는 데 유용해요!
• ⏳ 일반적인 큐(Queue)와 다르게, 우선순위를 기준으로 요소를 정렬하여 처리해요.

 

📌 Python에서 우선순위 큐 구현

import heapq  # 힙을 이용한 우선순위 큐

pq = []
heapq.heappush(pq, (1, '응급 환자'))  # (우선순위, 데이터)
heapq.heappush(pq, (3, '일반 환자'))
heapq.heappush(pq, (2, '보통 환자'))

while pq:
    print(heapq.heappop(pq))  # 우선순위가 가장 높은 데이터부터 출력

 

➡ 출력:

(1, '응급 환자')
(2, '보통 환자')
(3, '일반 환자')

---

 

 

🚀 2. 힙(Heap)이란?

**힙(Heap)**은 완전 이진 트리(Complete Binary Tree) 기반의 자료구조로, 항상 최댓값 또는 최솟값이 루트에 위치하는 특징이 있어요.

 

📌 힙의 종류

• 최소 힙(Min Heap): 루트 노드가 가장 작은 값을 가짐.
• 최대 힙(Max Heap): 루트 노드가 가장 큰 값을 가짐.

 

💡 힙의 특징

• 🚀 삽입, 삭제 연산이 O(log n)의 시간복잡도를 가짐 → 매우 효율적!
• 🔄 이진 트리를 사용하여 자동 정렬됨 → 최소/최대 값을 빠르게 찾을 수 있음.

 

📌 Python의 heapq 모듈을 활용한 최소 힙 구현

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)

print(heapq.heappop(heap))  # 최소값(1) 출력

➡ 출력: 1

 

📌 최대 힙을 구현하려면? (음수 활용)

import heapq

max_heap = []
heapq.heappush(max_heap, -5)  # 음수를 사용하여 최대 힙처럼 동작
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -3)

print(-heapq.heappop(max_heap))  # 최대값(5) 출력

➡ 출력: 5

---

 

 

🚀 3. 우선순위 큐와 힙의 시간복잡도 비교

 

연산 종류 우선순위 큐(정렬된 리스트) 힙(Heap)

삽입(Insert)	O(n)	O(log n)
삭제(Delete)	O(1)	O(log n)
최댓값/최솟값 검색	O(1)	O(1)

➡ 힙을 사용하면 삽입과 삭제 연산이 O(log n)으로 훨씬 빠릅니다!

---

 

 

🚀 4. 우선순위 큐의 활용 예시

 

📌 우선순위 큐는 어디에서 사용될까요?

1. 다익스트라 알고리즘(Dijkstra’s Algorithm) → 최단 경로 탐색에서 사용
2. 이벤트 스케줄링(Event Scheduling) → 예약 시스템, 운영체제의 작업 관리
3. 데이터 스트림 처리 → 대량의 데이터에서 특정 개수만 유지할 때
4. 캐싱 시스템(Cache System) → 가장 오래된 데이터를 우선 제거하는 경우

➡ 우선순위 큐는 알고리즘 문제 해결에서 매우 중요한 역할을 합니다! 😊

---

 

 

✅ 마무리 정리

• 우선순위 큐(Priority Queue)는 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조입니다.
• 힙(Heap)은 완전 이진 트리를 기반으로 하는 자료구조로, 최소/최대 값을 빠르게 찾을 수 있습니다.
• Python의 heapq 모듈을 사용하면 효율적인 우선순위 큐를 구현할 수 있습니다.
• 다익스트라 알고리즘, 예약 시스템, 데이터 스트림 처리 등 다양한 곳에서 활용됩니다.