👉 [CS] 우선순위 큐

우선순위 큐

우선순위 큐(Priority Queue)는 데이터를 저장하고, 꺼내올 때 우선순위에 따라 처리하는 자료구조이다.

일반적으로는 힙(Heap)이라는 자료구조를 이용하여 구현된다. (우선순위 큐 != 힙)

 

우선순위 큐는 일반 큐와 달리, 데이터가 들어올 때마다 우선순위를 비교하여 적절한 위치에 삽입하거나, 이미 삽입된 데이터 중 가장 우선순위가 높은 데이터를 먼저 꺼내오는 동작을 수행한다.

 

우선순위 큐는 다양한 분야에서 사용됩니다.

 

예를 들어, 다익스트라 알고리즘과 같은 최단 경로 알고리즘에서는 우선순위 큐를 이용하여 다음으로 방문할 노드를 선택한다.

또한, 운영 체제에서는 프로세스 스케줄링을 위해 우선순위 큐를 사용한다.

 

우선순위 큐는 일반적으로 삽입과 삭제 연산의 시간복잡도가 O(log n)입니다. 트리 구조이기 때문...

 

우선순위 큐를 위한 힙(Heap) 정리

Heap(힙)은 트리(Tree) 자료구조의 일종으로, 우선순위 큐와 같은 자료구조를 구현하는 데에 사용된다.

Heap은 다음과 같은 특성이 있다.

• 완전 이진 트리(Complete Binary Tree)의 형태. 힙(Heap)은 완전 이진 트리(Complete Binary Tree)의 한 종류
• 모든 부모 노드의 값은 자식 노드의 값보다 크거나 작다. 이를 최대 힙(Max Heap) 또는 최소 힙(Min Heap)이라고 부름.

힙은 일반적으로 배열(Array)로 구현된다. 이때, 부모 노드와 자식 노드 간의 관계는 다음과 같이 인덱스를 이용하여 계산된다.

• 부모 노드의 인덱스 = (자식 노드의 인덱스 - 1) / 2
• 왼쪽 자식 노드의 인덱스 = (부모 노드의 인덱스 * 2) + 1
• 오른쪽 자식 노드의 인덱스 = (부모 노드의 인덱스 * 2) + 2

구현을 편하게 하기 위해 0 번째 배열을 사용하지 않기도 하며, 이때는 아래와 같이 쓰인다.

• 부모 노드의 인덱스 = (자식 노드의 인덱스) / 2
• 왼쪽 자식 노드의 인덱스 = (부모 노드의 인덱스 * 2)
• 오른쪽 자식 노드의 인덱스 = (부모 노드의 인덱스 * 2) + 1

최소힙 트리 예시와 배열 표기

 

 

힙으로 우선순위 큐 구현

예를 들어, 최소값 우선순위 큐를 구현한다고 가정. 이때, 힙을 이용하여 구현할 수 있다.

1. 최소 힙(Min Heap)을 생성. 이때, 위 사진처럼 배열로 구현 가능.
2. 삽입 연산을 구현. 이때, 데이터를 힙의 마지막 노드에 추가하고, 힙의 특성에 맞게(우선 순위) 올라가면서 값을 비교하여 위치를 조정.
3. 삭제 연산을 구현. 이때, 힙의 최상위 노드(루트 노드)를 삭제하고, 아래로 내려가면서 값을 비교하여 위치를 조정. 이때, 삭제된 노드는 우선순위가 가장 낮은 데이터이므로, 이를 반환한다.

아래는 파이썬 코드로 구현한 예시로, heapq 내장모듈을 활용했다.

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]