[CLRS] [6-5] Priority queues(우선순위 큐)

1. Priority Queue(우선순위 큐)?

- 우선 Priority Queue를 설명하기 전에, Queue에 대해서 설명하고자 한다.

- Queue는 FIFO(FIrst In First Out) 즉 선입선출, 먼저 집어 넣은 데이터가 먼저 나오는 자료구조이다.

- 하지만 Priority Queue는 들어간 순서에 상관없이, 우선순위가 높은 데이터부터 먼저 나오는 것을 의미한다.

2. 우선순위 큐의 메소드

- 우선순위 큐의 메소드는 크게 3가지가 존재한다.

i) insert() : queue에 데이터를 삽입한다.

ii) delete() : queue에서 최대 우선순위 데이터를 삭제하고 그 값을 반환한다.

iii) peek() : queue에서 최대 우선순위 데이터를 반환한다.

 

2.1. Qriority Queue 전체 코드

from collections import deque

def max_heapify(arr,i):
    left_node = 2*i
    right_node = 2*i+1

    if (left_node <= len(arr)-1) and arr[left_node] > arr[i]:
        largest = left_node
    else:
        largest = i
    if (right_node <= len(arr)-1) and arr[right_node] > arr[largest]:
        largest = right_node

    if largest != i :
        arr[i],arr[largest] = arr[largest], arr[i]
        max_heapify(arr,largest)

class priority_queue:

    def __init__(self):
        self.queue = deque([0])

    def peek(self):
        if len(self.queue) <= 1:
            raise IndexError('queue is empty')
        return self.queue[1]

    def delete(self):
        max = self.peek()
        self.queue[1] = self.queue[-1]
        self.queue.pop()
        max_heapify(self.queue,1)
        return max

    def insert(self,data):
        self.queue.append(data)
        i = len(self.queue) - 1
        while i > 1 and self.queue[i // 2] < self.queue[i]: 
            self.queue[i // 2], self.queue[i] = self.queue[i], self.queue[i // 2]
            i = i // 2

2.2. peek()

- 간단하게 우선순위 데이터를 반환하는 메소드이다.

- 우선순위 데이터는 root-node에 있는 데이터이기 때문에 인덱스가 1인 데이터를 반환하기만 하면 된다.

- 만일 heap이 empty면 비어있다는 걸 표시해준다.

    def peek(self):
        if len(self.queue) <= 1:
            raise IndexError('queue is empty')
        return self.queue[1]

 

2.3. delete()

- 우선순위 데이터를 heap에서 제거한 후 그 데이터를 반환하는 메소드이다.

- 이는 root-node(우선순위 데이터)와 가장 마지막 데이터를 바꿔준 후(Swap)

- 우선순위 데이터를 pop()해주고, max_heapify()를 root-node에 대해 실행하면 된다. 

    def delete(self):
        max = self.peek()
        self.queue[1] = self.queue[-1]
        self.queue.pop()
        max_heapify(self.queue,1)
        return max

 

2.4. insert()

- 데이터를 Qriority Queue에 삽입하는 메소드인데,

- 가장 끝에 삽입하게 된다. 그 후, 부모노드와 비교하여 max-heap을 만들어 나가면 된다. O(logn)

    def insert(self,data):
        self.queue.append(data)
        i = len(self.queue) - 1
        while i > 1 and self.queue[i // 2] < self.queue[i]: 
            self.queue[i // 2], self.queue[i] = self.queue[i], self.queue[i // 2]
            i = i // 2

 

3. 파이썬에서의 heapq

- 파이썬에서 heapq 모듈은 Priority Queue 알고리즘을 제공한다. 

- min-heap의 형태로 주어진다.

- 인덱스는 0부터 시작을 한다.

 

3.1. heapq 함수

i) heapq.heappush(heap,item) : heap에 item을 삽입한다.

ii) heapq.heappop(heap) : heap에서 가장 작은 원소를 pop하고 return한다.

iii) heapq.heapify(x) : x라는 배열을 heap으로 변환한다. (O(N)이 걸린다.)