Priority Queue

• Priority Queue : 다익스트라 알고리즘, Huffman 코딩, Prim 알고리즘 등 다양한 알고리즘에서 활용되는 DS이다. 보통 Queue와 달리 우선순위가 높은 원소가 먼저 나오도록 정렬되어 있다.

---

파이썬에서 제공하는 heapq 클래스는 다음과 같다.

__all__ = ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge',
           'nlargest', 'nsmallest', 'heappushpop']

• heappush(heap, item) : heap에 item을 append한 후 heapify. 힙구조는 유지된다.

• heappop(heap) : heap의 가장 작은 값을 제거하면서 리턴한다. 만약 힙이 비어있으면 적절한 인덱스 에러를 호출하며, 마찬가지로 힙구조는 유지된다.

  • 먼저 heap.pop()을 통해 트리상 맨 마지막 값을 lastelt에 넣고, 만약 heap이 pop 이후에도 있다면 heap[0]을 returnitem으로, 그리고

---

따라서, Heapq를 사용하여 PQ를 구현하면

import heapq

class PriorityQueue():
	def __init__(self):
    	self.queue = []
        self.count = 0
        
    def enqueue(self, priority, v):
    	self.count += 1
        heapq.heappush(self.queue, (priority, self.count, v))
    
    def dequeue(self):
    	heapq.heappop(self.queue)
        
    def display(self):
    	print(self.queue)
        
if __name__ == "__main__":
	pq = PriorityQueue()
    print(pq.enqueue(1, 'test1'))
    ...
    pq.display()