파이썬) 우선순위 큐

우선순위 큐란 기존의 선입선출의 특성을 따르지 않고, 원소들의 우선순위에 따라 큐에서 빠져나오는 방식을 가진 큐이다.

큐의 원소가 3,6,8,5로 무작위 순서로 구성되있을 우선순위를 숫자가 작은 원소가 먼저 빠져나온다 가정하면 3,5,6,8 식으로 빠져나올 것이다.

 

우선순위 큐를 구현할 때 두가지 경우가 가능한데

 

1. enqueue할 때 우선순위를 유지하도록

 

2. dequeue할 때 우선순위 높은 것을 선택하도록

 

이 두 방법 중 시간적 측면에서 유리한 방법은 첫번째이다. 그 이유는 두번 째 경우는 삭제할 원소를 찾으려면 모든 원소를 들여다봐야하기 때문에 큐의 길이에 비례하는 시간을 가진다. 하지만 첫번 째 경우는 삽입 시 모든 원소를 들여다볼 필요는 없기 때문에 조금 더 유리하다.

 

큐를 구현할 때 배열 또는 연결 리스트로 구현이 가능한 데 우선순위 큐를 구현할 때는 연결 리스트가 시간적 측면에서 조금 더 유리하다. 그 이유는 우선순위 큐에 원소를 삽입할 때 원소의 우선순위를 비교해서 삽입하기 때문에 중간에 삽입하는 경우가 많을 것이다. 배열의 중간에 삽입하게 되면 그 뒤의 원소를 한칸 씩 밀어야 하지만, 연결 리스트 같은 경우는 링크를 새로 이어주기만 하면 되기 때문에 유리하다.

 

숫자가 작은 원소가 우선순위인 큐를 코드로 구현하면 다음과 같다.

class PriorityQueue:

    def __init__(self):
        self.queue = DoublyLinkedList()


    def size(self):
        return self.queue.getLength()

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, x):
        newNode = Node(x)
        curr = self.queue.head
        while curr.next.data !=None  and x< curr.next.data:
            curr=curr.next
            self.queue.insertAfter(curr, newNode)
           
           
    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())

    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data

삽입 시 원소의 우선순위를 유지하도록 하는 enqueue 코드 부분을 보면 삽입할 원소 x와 삽입되있는 원소 curr을 우선순위에 맞을 때까지 비교를 한다. 그 후 curr < x < curr.next에 조건이 맞으면 그 자리에 삽입을 한다. 그 외 dequeue, peek은 일반 큐와 동일하다.