Python으로 구현하는 자료구조 : Queue (3) Priority Queue

이번 포슽팅에서는 자료구조 Queue의 한 종류인 Priority Queue(우선순위 큐)에 대한 특징을 살펴보고

파이썬으로 Priority Queue에 원소를 삽입, 삭제하는 코드를 짜보도록 하겠습니다.

---

# Priority Queue란

Priority Queue(우선순위 큐)는 Dijkstra 알고리즘, Huffman 코딩, Prim 알고리즘 등 다양한 알고리즘에서 활용되는 자료구조입니다. Priority Queue의 각 원소들에게는 우선순위 값이 있으며, 이 값이 낮을 수록 급하게 처리해야 하는 데이터입니다. 보통 Queue는 들어오는 순서대로 원소들을 저장하지만, Priority Queue에서는 우선순위가 높은 원소가 먼저 나오도록 정렬되어 있습니다.

# Priority Queue 구현하기

# 파이썬 코드 - Heapq 모듈 사용하기

우선순위가 같은 원소들에 대해서는 순서 보존을 위해 들어온 순서대로 count 값도 저장합니다. Priority Queue에서는 queue에 데이터를 heappush할 때, 입력한 priority를 작은 순서대로 정렬한 다음, self.count가 작은 순서대로 정렬합니다. 따라서 같은 우선순위를 가진 원소더라도 데이터가 들어온 순서대로 dequeue가 가능해집니다.

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'))
    print(pq.enqueue(4, 'test2'))
    print(pq.enqueue(3, 'test3'))
    print(pq.enqueue(1, 'test4'))
    print(pq.enqueue(2, 'test5'))
    print(pq.enqueue(1, 'test6'))
    pq.display() # [(1, 1, 'test1'), (1, 4, 'test4'), (1, 6, 'test6'), (4, 2, 'test2'), (2, 5, 'test5'), (3, 3, 'test3')]