15. 우선 순위 큐(Priority queue), 파이썬

파이썬에는 queue.PriorityQueue가 기본 모듈로 있습니다. @,.@
PriorityQueue의 베이스인 heapq 모듈도 있습니다. ~!

 

그렇기 때문에 만들 필요가 없는 것이고,
(파이썬의 배터리 인클루드~!)

 

또 제대로 만들려면 힙을 이용하는 게 맞습니다만,
간단하게 흉내만 내 보겠습니다. 

 

혹시 힙이 궁금하시면 다음 링크를 참고하십시오. 

https://comdoc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9D%98-heapq-%EB%AA%A8%EB%93%88

 

---------------------------------

 

보통 큐에서는 먼저 삽입한 요소부터 삭제됩니다. 
하지만 우선순위를 기준으로 요소를 삭제해야 하는 경우도 있습니다. 

 

대표적인 예가 응급실이죠. 
환자의 상태를 고려해서 우선순위를 정하고,
우선순위가 높은 환자가 먼저 진료를 받겠습니다. 
우선순위가 같은 경우는 순서대로 진료를 받도록 합니다. 
우선순위 코드는 1자리의 정수로 낮을수록 응급 상황입니다. 

 

13. 큐(https://comdoc.tistory.com/entry/13-큐queue-ADT-파이썬with-Python)에서
작성했던 코드를 약간만 수정합니다. 

 

class Patient:
    def __init__(self, name, code):
        self.name = name
        self.code = code


class PriorityQueue:
    def __init__(self):
        self.data = []

    def enqueue(self, element):
        self.data.append(element)

    def dequeue(self):
        entry = 0
        for i in range(len(self.data)):
            if self.data[i].code < self.data[entry].code:
                entry = i
        return self.data.pop(entry)

    def front(self):
        return self.data[0]

    def back(self):
        return self.data[len(self.data)-1]

    def is_empty(self):
        return len(self.data) == 0

    def show(self):
        for patient in self.data:
            print(patient.name, patient.code)


er_que = PriorityQueue()
er_que.enqueue(Patient('Kim', 5))
er_que.enqueue(Patient('Johns', 4))
p = er_que.dequeue()
print(p.name, p.code)
er_que.enqueue(Patient('White', 1))
p = er_que.dequeue()
print(p.name, p.code)
er_que.enqueue(Patient('Brown', 6))
er_que.enqueue(Patient('Smith', 1))
p = er_que.dequeue()
print(p.name, p.code)
p = er_que.dequeue()
print(p.name, p.code)
p = er_que.dequeue()
print(p.name, p.code)

중간중간에 넣었다 뺐다 정신이 없지만
(실제 응급실은 더 정신이 없겠죠?)
순서대로 잘 작동됩니다. 

Johns 4
White 1
Smith 1
Kim 5
Brown 6

 

파이썬에는 __str__ 메서드가 있습니다. 
이 메서드를 정의해 두면, 정의한 대로 print 됩니다.

class Patient:
    def __init__(self, name, code):
        self.name = name
        self.code = code

    def __str__(self):
        return f'{self.name} {self.code}'


class PriorityQueue:
    def __init__(self):
        self.data = []

    def enqueue(self, element):
        self.data.append(element)

    def dequeue(self):
        entry = 0
        for i in range(len(self.data)):
            if self.data[i].code < self.data[entry].code:
                entry = i
        return self.data.pop(entry)

    def front(self):
        return self.data[0]

    def back(self):
        return self.data[len(self.data) - 1]

    def is_empty(self):
        return len(self.data) == 0

    def show(self):
        for patient in self.data:
            print(patient.name, patient.code)


er_que = PriorityQueue()
er_que.enqueue(Patient('Kim', 5))
er_que.enqueue(Patient('Johns', 4))
print(er_que.dequeue())
er_que.enqueue(Patient('White', 1))
print(er_que.dequeue())
er_que.enqueue(Patient('Brown', 6))
er_que.enqueue(Patient('Smith', 1))
print(er_que.dequeue())
print(er_que.dequeue())
print(er_que.dequeue())

Johns 4
White 1
Smith 1
Kim 5
Brown 6

 

heapq를 이용해 보겠습니다. 

from heapq import heappush, heappop

er_que = []
heappush(er_que, (5, 'Kim'))
heappush(er_que, (4, 'Johns'))
print(heappop(er_que))
heappush(er_que, (1, 'White'))
print(heappop(er_que))
heappush(er_que, (6, 'Brown'))
heappush(er_que, (1, 'Smith'))
print(heappop(er_que))
print(heappop(er_que))
print(heappop(er_que))

(4, 'Johns')
(1, 'White')
(1, 'Smith')
(5, 'Kim')
(6, 'Brown')

힙큐를 씁시다. ~!