Priority Queue

이번에 살펴볼 자료구조는 Priority Queue(우선순위 큐)로써, Dijkstra 알고리즘, Huffman 코딩, Prim 알고리즘 등 다양한 application에 적용됩니다. 작동 원리는 굉장히 심플합니다. PQ(Priority Queue)의 각 원소들은 priority값을 가지고 있습니다. 이 값은 낮을수록 급하게 처리되어야 한다는 의미이므로, 보통 queue에서는 들어온 순서대로 원소들을 저장하고 있지만, PQ에서는 낮은 priority의 원소가 먼저 나오도록 정렬되어 있다고 보시면 됩니다.

위의 그림처럼 비록 늦게 들어온 원소라도 낮은 priority를 갖는다면 queue의 맨 앞쪽에 위치하게 되는 것입니다. 보통 PQ를 구현하는 background 자료구조는 Heap을 사용합니다. Min Heap(최소값이 가장 먼저 나오게끔 하는 자료구조) 자체가 이미 priority sorting기능을 제공하기 때문에, 나머지 노드 부분만 묶어서 관리한다면 priority queue가 될 수 있는 것입니다 :)

먼저 Python의 내장 라이브러리인 heapq라는 친구를 살펴보겠습니다.

import heapq

heapq는 기본적으로 python의 list 기반으로 동작하기 때문에, 별도로 자료 구조를 생성할 필요가 없습니다. 그냥 list를 저장소로 사용하되, heapq의 함수들을 사용해서 자료를 조작하시면 됩니다.

pq = []

우리가 (priority, value)의 tuple 형태로 값을 넣어준다고 합시다. 랜덤하게 10개의 input을 만들어 보겠습니다.

>>> import random
>>> val_node_pairs = [(random.randint(0, 10), random.randint(0, 10)) for i in range(10)]
>>> print val_node_pairs
[(3, 7), (8, 9), (2, 1), (4, 4), (1, 10), (4, 7), (8, 2), (4, 10), (10, 6), (10, 8)]

그럼 이제 이 input들을 넣어서 어떤 결과가 나오는지 확인해 봅시다.

>>> for pair in val_node_pairs:
...     heapq.heappush(pq, pair)

>>> print heapq.nsmallest(len(pq), pq)
[(1, 10), (2, 1), (3, 7), (4, 4), (4, 7), (4, 10), (8, 2), (8, 9), (10, 6), (10, 8)]

nsmallest함수는 n개의 수를 가장 작은 순서대로 뽑아서 list를 리턴하는 함수입니다. 결과를 보시면 아시겠지만 정렬 자체는 잘 되어있음을 확인할 수 있죠? 그런데 문제점 세 가지나 있습니다.

Sorting이 UNSTABLE합니다. 즉, 동일한 priority를 가졌을 때, 순서 보존이 안되고 value까지도 정렬해버린다는 것입니다.
PQ에 같은 value를 가지는 원소를 넣었을 때, 즉 새로운 priority로 업데이트가 불가능합니다.
PQ에서 특정 value를 가지는 원소를 지울 수 없습니다.

이런 것들이 단순히 heapq를 PQ로 사용하기에는 부적절하다는 결론이 나옵니다! 따라서 우리가 직접 한번 멋진 PQ를 구현해 보도록 합시다 :)

import heapq #내부적으로 heapq라이브러리를 사용하기 때문에 import합니다.
class PriorityQueue:
    pq = [] 
    elements = {}
    counter = 0 #이것을 통해서 stable sorting이 가능해집니다!
    
    def insert(self, priority, value):
        if value in self.elements:
        	#UPDATE하는 경우이면, 기존 priority보다 작을 시에 UPDATE합니다.
            if priority < self.elements[value][0]:
                self.delete(value)
            else:
                return
        entry = [priority, self.counter, value]
        self.counter += 1
        self.elements[value] = entry
        heapq.heappush(self.pq, entry)
    
    def delete(self, value):
    #지우는 것은 단순히 해당 entry의 value를 None으로 설정합니다.
    #pq에서 지우지 않는 이유는 heap의 특성을 보존하기 위해서입니다.
        entry = self.elements[value]
        entry[-1] = None
        
    def pop(self):
    #대신 pop을 하면서 deleted된 녀석들을 걸러줍니다.
        while self.pq:
            priority, counter, value = heapq.heappop(self.pq)
            if value != None:
                del self.elements[value]
                return priority, value
        raise KeyError('Pop from an empty PriorityQueue')    
    
    def size(self):
        return len(self.elements)

각 문제들의 해결방법은 아래와 같습니다.

먼저 Stable Sorting문제는 단순히 (priority, value)의 형태가 아닌, (priority, UNIQUE NUMBER, value)의 형태로, 하나를 넣을 때마다 UNIQUE NUMBER를 증가시키면, sorting을 할 때 나중에 넣은 것은 같은 priority를 가질 때 뒤로 밀려나게 됩니다 :)
UPDATE하는 문제는 넣는 부분에서 if문으로 해결했습니다. 기존의 것보다 priority가 더 클 시에는 UPDATE할 필요가 없으므로 return으로 함수를 끝내버립니다.
DELETE하는 문제는 바로 pq에서 지우지 않고, 일단 해당 원소의 value를 None으로 바꾼 상태로 둡니다. 그 이유는 pq에서 원소를 지우게 되면 heap구조가 깨지기 때문에 이를 막기 위해서입니다. 물론 이것은 결국 자주 지웠을 때 성능의 저하로 나타나게 되지만, 매번 지우고 heap을 다시 만들고 하는 것보다는 나을 것입니다.

그럼 이제 우리가 구현한 PriorityQueue를 시험해 봅시다 :)

>>> pq2 = PriorityQueue() #비어있는 PQ를 만들어주고,
>>> for pair in val_node_pairs:
...     pq2.insert(*pair) #test input을 넣어줍니다.

## Pop을 계속해나가면서 결과를 출력합니다.
>>> while pq2.size() > 0:
...     print pq2.pop()
(1, 10)
(2, 1)
(3, 7)
(4, 4)
(8, 9)
(8, 2)
(10, 6)
(10, 8)

어때요? value가 같은 input들은 priority가 낮은 것들만 살아남았고, 또한 sorting의 stability도 잘 보존됨을 확인할 수 있죠? :) 휴.. 아주 어려운 예제였습니다 :)

Jacob's Coding Playground

Recommended Posts

Recent Posts