Priority Queue

Priority Queue

• 대표적인 비선형 자료구조 입니다.
• 큐와 이름이 유사하지만 동작 방식은 다릅니다. 큐는 먼저 삽입한 값이 먼저 나오는 구조를 가지지만 우선순위 큐는 삽입한 값이라고 먼저 나오는 것이 아닌 우선순위가 높은 값이 먼저 출력됩니다. 우선순위는 프로그래머가 정하지만 대표적인 우선순위는 값의 크기에 따라 정하는 경우가 많습니다. 값이 클경우 우선순위가 높거나 값이 작을 경우 우선순위가 낮은 경우 입니다.

Priority Queue를 구현

import heapq

class PriorityQueue:
    '''
    우선순위 큐를 힙으로 구현합니다
    '''
    def __init__(self) :
        self.heap = []

    def push(self, value) :
        '''
        우선순위 큐에 value를 삽입합니다.
        '''
        heapq.heappush(self.heap, value)

    def pop(self) :
        '''
        우선순위가 가장 높은 원소를 제거합니다.
        '''
        if len(self.heap) > 0:
            return heapq.heappop(self.heap)

    def top(self) :
        '''
        우선순위가 가장 높은 원소를 반환합니다. 만약 우선순위 큐가 비어있다면 -1을 반환합니다.
        '''

        if len(self.heap) == 0:
            return -1

        return self.heap[0]

pq = PriorityQueue()


pq.push(3)
pq.push(4)

pq.push(1)
pq.push(2)
pq.push(5)

print(pq.pop())

heap으로 priority queue를 구현하는 이유

• 우선순위큐를 힙자료구조로 구현하는 이유는 시간복잡도를 생각해보면 알 수 있다.
• 우선순위큐를 배열을 이용해서 구현한다면 삽입에는 O(1)의 시간복잡도, n개의 데이터에서 최대 또는 최소의 값을 찾아야 하므로 출력에는 O(n)의 시간복잡도가 걸린다. 그리고 출력후에는 배열에서 제거를 하고 뒤에 있는 요소들을 앞으로 이동시켜야 하는 부담이 있다.
• 하지만 이미 규칙을 갖고 최대값과 최소값을 찾기 쉽게 구현된 자료구조를 이용하면 이 문제를 해결할 수 있다.
• heap에서 자료는 제거하는 방법은 O(1) 삽입은O(logN)걸린다. 이유는 트리의 높이와 비례하기 때문에 logN이 걸린다.