우선순위 큐

우선순위 큐의 정의

우선순위 큐는 들어오는 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나가는 자료구조.

우선순위 큐는 힙(Heap)을 이용하는 게 제일 효율적.

(큐는 먼저 들어오는 데이터가 먼저 나가는 선입선출 (FIFO) 형식의 자료구조)

 

Heap의 정의

완전이진트리 형태의 자료구조

완전이진트리 : 마지막 레벨을 제외한 모든 레벨이 모두 채워져 있고, 마지막 레벨은 왼쪽부터 채워져 있어야 함.

 

Heap의 종류

최대 힙(Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 큰 구조

최소 힙(Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작은 구조

 

힙 자료 구조

heapq 모듈은 이진트리 기반의 최소 힙 자료구조 제공함.

ex) 힙에 원소 추가 및 삭제

from heapq import heappush, heappop

heap= []
heappush(heap, 4)
heappush(heap, 8)
heappush(heap, 6)
heappush(heap, 3)
print(heap)

출력 결과로 [3, 4, 6, 8] 나옴.

 

heappop(heap)

결과로 3 나옴.

 

print(heapq)

결과로 [4, 6, 8] 나옴

 

 

heapq는 list와 tree의 장점 모두 사용함.

1. 트리 구조를 사용함.

요소 삽입 및 최소값 제거 시 발생하는 요소의 검색 및 스왑의 횟수가 리스트 사용할 때보다 적음.

2. 리스트를 사용함.

완전 이진트리는 리스트로 코딩 가능.

리스트가 클래스보다 빠름.

 

기존 리스트를 힙으로 변환

heapify() 함수를 사용하면 됨.

ex)

from heapq import heapify

heap = [5,6,8,2,4,1]
heapify(heap)
print(heap)

결과로 최소힙이 적용된 [1, 2, 4, 5, 6, 8] 나옴.

---

heapq 모듈들 응용 방법

최대 힙

 

import heapq

n = [2, 5, 4, 9, 3, 7]
heap = []

for i in n :
	heapq.heappush(heap, (-i, i))
  
  while heap:
  	print(heapq.heappop(heap)[1])

결과로

9

7

5

4

3

2

 

힙에 원소를 추가할 때 (-원소의 값, 원소의 값)으로 저장하면

-원소의 값(음수 값)으로 최소 힙이 되므로, 원래 양수의 값에서는 최대 힙이 됨.

 

---

출처

https://velog.io/@plate0113/Python-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-heapq

https://velog.io/@yun8565/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-Priority-Queue