[Algorithm] 우선순위 큐(Priority Queue), 힙(Heap)

✨우선순위 큐(Priority Queue)

평범한 큐나 스택과 비슷한 축약 자료형이다.
각 원소들은 우선순위를 갖고 있다. 
높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다.
자료구조 힙을 통하여 구현된다

 

✨힙(Heap)

최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리
부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙'
부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙'

 

 

✨Python PriorityQueue 

from queue import PriorityQueue

q=PriorityQueue()
q.put(5)
q.put(3)
q.put(4)

print(q.get())
#출력: 3

 

(우선순위,값)튜플 형태 추가

from queue import PriorityQueue

q=PriorityQueue()
q.put((5,'eee'))
q.put((3,'qqq'))
q.put((4,'www'))

print(q.get()[1])
#출력: qqq

 

✨Python heapq

import heapq

hq=[]
heapq.heappush(hq,1)#minheap형태로 1push
heapq.heappush(hq,2)#minheap형태로 1push
heapq.heappop(hq)   #1pop

 

import heapq

hq=[]
heapq.heappush(hq,(-1,1))#maxheap형태를 음수를 활용하여 만든다
heapq.heappush(hq,(-2,2))#maxheap형태를 음수를 활용하여 만든다
heapq.heappop(hq)[1]     #2pop

 

 

 

 

 

🎈참고자료

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

https://ko.wikipedia.org/wiki/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84_%ED%81%90

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