파이썬 우선순위 큐.

https://docs.python.org/2/library/heapq.html

여기껄 클래스화시켰다. 큐의 순서는 출력해보면 알겠지만 우선순위에 따라서 출력된다.

# -*- encoding: cp949 -*-
from heapq import *
class priority_queue():
    def __init__(self):
        self.pq = []                         # list of entries arranged in a heap
        self.entry_finder = {}               # mapping of tasks to entries
        self.REMOVED = '<removed-task>'      # placeholder for a removed task

    def put(self, task, priority=0):
        'Add a new task or update the priority of an existing task'
        if task in self.entry_finder:
            self.remove(task)
        self.entry = [task, priority]
        self.entry_finder[task] = self.entry
        heappush(self.pq, self.entry)

    def remove(self, task):
        'Mark an existing task as REMOVED.  Raise KeyError if not found.'
        self.entry = self.entry_finder.pop(task)
        self.entry[-1] = self.REMOVED

    def pop(self,):
        'Remove and return the lowest priority task. Raise KeyError if empty.'
        while self.pq:
            self.task, self.priority = heappop(self.pq)
            if self.task is not self.REMOVED:
                del self.entry_finder[self.task]
                return self.task
        raise KeyError('pop from an empty priority queue')
    
    def __str__(self):
        return str(self.pq)


q = priority_queue() #인스턴스 만듬.
q.put(10,1) #원소 10을 넣고 우선순위를 1로 넣음. (우선순위가 낮을수록 큐의 가장 윗부분에 오게됨.)
q.put(5,0) #원소 5를 넣고 우선순위 0을 넣음. 나중에 들어갔음에도 10보다 더 위에있게됨.
q.put(20,3) 
print q #확인용
print q.pop() #pop 확인용
print q