어제는 힙 자료구조를 구현했었다. 오늘은 이를 이용해 우선순위 큐를 구현하는데, 우선순위 큐는 힙을 이용하면 간단하게 구현이 가능하다.
우선 힙은 완전이진트리의 형태를 갖는 비선형 자료구조이고 큐는 FIFO(first in first out) 의 기능을 하는 선형자료구조라는 점에서 가장 차이가 크다.
우선순위 큐는 자료구조는 큐를 따르지만 데이터의 주어진 우선순위에 따라 데이터가 pop되는 순서가 달라지는 자료구조를 말한다.
우선순위 큐에서 힙을 이용하는 이유는 우선순위가 가장 높은 데이터를 가장 먼저 pop 시키기 때문에 최소값이나 최대값을 반드시 루트 노드에 배치시키는 힙과 궁합이 잘맞기 때문이다. (물론 속도도 빠르다. 힙이 O(logN)의 시간복잡도를 가지기 때문에)
큐를 우선순위를 기준으로 heap으로 만들어주면 우선순위 큐 구현이 된다.
import heapq
class PriorityQueue(object):
def __init__(self):
self.queue = [] # 큐 리스트를 만들어줌.
self._index = 0 # 지금 당장은 활용하지 않지만 index값을 지정해 줄 필요가있음
def push(self,item, priority):
heapq.heappush(self.queue, (-priority, self._index, item))
# 힙은 최소값이 루트노드로 가기 때문에 priority에 - 를 해주어서 우선순위가 높을수록 작은 값을 갖게 해줌
self._index += 1
def pop(self):
return heapq.heappop(self.queue)[-1]
# pop값의 item을 return 해줌
class Item:
def __init__(self, name):
self.name = name
def __repr__(self):
return "Item({0!r})".format(self.name)
def test_priority_queue():
q=PriorityQueue()
q.push(Item("test1"), 1)
q.push(Item("test2"), 4)
q.push(Item("test3"), 3)
q.push(Item("test4"), 2)
print(str(q.pop()))
if __name__ == "__main__":
test_priority_queue()
우선순위 큐를 배열, 연결리스트, 힙 세 가지 방식으로 구현할 수 있는데 각 방식의 장 단점을 알아두어야 제대로 우선순위 큐를 알고 있다고 할 수 있다.
우선 배열과 연결리스트는 삽입 과정에서 해당 원소의 우선순위가 들어갈 위치를 찾기 위해 최악의 경우 모든 원소를 모두 순회하며 검색을 해야 하기 때문에 O(n)의 삽입 시간복잡도를 갖습니다. 반면 삭제에는 O(1)로 끝의 데이터를 삭제해버리면 됩니다.
추가로 배열은 삽입을 하면서 인덱스를 재조정하기 때문에 같은 O(n) 이지만 훨씬 더 속도가 느려지게 됩니다.
반면 힙은 삽입과 삭제 모두 O(logN)의 시간복잡도를 보장하기 때문에 훨씬 안정적이라고 할 수 있습니다. 삽입 시 끝의 노드로 값이 들어가고 O(logN)의 시간 내에 루트 노드를 찾아갑니다. 삭제 또한 루트 노드를 삭제하면 끝의 노드를 루트 노드로 옮기고 O(logN)의 시간 안에 힙 조정이 완료됩니다.
