[Python] 우선순위 큐

728x90

1. 우선순위 큐란?

우선순위 큐(Priority Queue)는 각 요소가 우선순위를 가지고 있는 데이터 구조로, 일반적인 큐(FIFO 구조)와는 달리, 데이터가 삽입된 순서가 아닌 우선순위에 따라 요소를 처리합니다. 우선순위가 높은 요소가 먼저 처리되며, 동등한 우선순위를 가진 요소는 대개 삽입된 순서대로 처리됩니다.

즉, 우선순위 큐는 우선순위에 따라 데이터 처리를 효율적으로 관리하는 데 유용한 자료구조라고 할 수 있겠습니다.

2. 우선순위 큐의 주요 특징

우선순위 큐의 주요 특징은 다음과 같습니다.

우선순위 기반 처리: 높은 우선순위를 가진 요소가 가장 먼저 처리됩니다.
동적 삽입/삭제: 새로운 요소의 삽입과 우선순위가 높은 요소의 삭제가 효율적으로 이루어집니다.
자료구조 기반: 일반적으로 힙(Heap)을 사용해 구현됩니다.

일반적으로 힙을 통해서 구현된다는 것의 의미는, 기존의 최소힙, 최대힙이 그냥 value에 따라서 정렬되었다면, 우선순위 큐는 입력한 우선순위를 기준으로 최소, 최대의 기준에 맞게 정렬한다는 뜻입니다.

3. 우선순위 큐 활용 사례

다익스트라 알고리즘
- 최단 경로를 찾는 알고리즘에서, 현재 노드에서 가장 작은 비용으로 갈 수 있는 노드를 우선적으로 탐색해야 합니다.
- 여기서 비용(distance)이 우선순위가 됩니다.
작업 스케줄링
- 운영체제에서 CPU 스케줄링 시, 긴급도가 높은 작업(우선순위가 높은 작업)을 먼저 처리해야 합니다.
시뮬레이션 시스템
- 사건(Event)이 발생하는 시뮬레이션에서, 이벤트 발생 시점(time)을 우선순위로 설정하여 가장 빠른 시점의 이벤트를 먼저 처리.
검색 문제
- 우선순위가 높은 데이터(예: 사용자 검색 기록에서 가장 관련 있는 결과)를 빠르게 제공.

4. 우선순위 큐 구현 코드

1)heapq 모듈을 이용한 구현

###입력
import heapq

# 우선순위 큐 초기화
priority_queue = []

# 요소 삽입 (우선순위, 값)
heapq.heappush(priority_queue, (1, 'Task 1'))  # 우선순위가 낮은 값이 먼저 처리됨
heapq.heappush(priority_queue, (3, 'Task 3'))
heapq.heappush(priority_queue, (2, 'Task 2'))

# 요소 삭제 (우선순위가 가장 높은 요소 제거)
while priority_queue:
    priority, task = heapq.heappop(priority_queue)
    print(f"Processing {task} with priority {priority}")

Processing Task 1 with priority 1
Processing Task 2 with priority 2
Processing Task 3 with priority 3

2)queue.PriorityQueue 클래스 이용

from queue import PriorityQueue

# 우선순위 큐 초기화
pq = PriorityQueue()

# 요소 삽입
pq.put((2, 'Task 2'))
pq.put((1, 'Task 1'))
pq.put((3, 'Task 3'))

# 요소 삭제
while not pq.empty():
    priority, task = pq.get()
    print(f"Processing {task} with priority {priority}")

5. PriorityQueue 클래스는 어떻게 구성되어있을까?

위에서 그냥 import 해서 쓴 priorityqueue는 어떻게 구성되어있을지 한번 살펴봅시다.

1)최소 힙

import heapq

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

    def push(self, priority, value):
        # (우선순위, 값) 형태로 최소 힙에 삽입
        heapq.heappush(self.heap, (priority, value))

    def pop(self):
        # 우선순위가 가장 높은 요소(최소 우선순위) 제거
        return heapq.heappop(self.heap)

    def peek(self):
        # 우선순위가 가장 높은 요소 확인 (삭제하지 않음)
        return self.heap[0]

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

# 예제 사용
pq = PriorityQueue()
pq.push(2, "Task 2")
pq.push(1, "Task 1")
pq.push(3, "Task 3")

while not pq.is_empty():
    priority, task = pq.pop()
    print(f"Processing {task} with priority {priority}")

2)최대

import heapq

class MaxPriorityQueue:
    def __init__(self):
        self.heap = []

    def push(self, priority, value):
        # 우선순위를 음수로 변환하여 최대 힙처럼 동작하게 만듦
        heapq.heappush(self.heap, (-priority, value))

    def pop(self):
        # 우선순위를 다시 양수로 변환하여 반환
        priority, value = heapq.heappop(self.heap)
        return -priority, value

    def peek(self):
        # 최우선순위 요소 확인
        priority, value = self.heap[0]
        return -priority, value

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

# 예제 사용
pq = MaxPriorityQueue()
pq.push(2, "Task 2")
pq.push(1, "Task 1")
pq.push(3, "Task 3")

while not pq.is_empty():
    priority, task = pq.pop()
    print(f"Processing {task} with priority {priority}")

5. 우선순위 큐의 시간 복잡도

다음으로 우선순위 큐의 시간 복잡도는 다음과 같이 정의할 수 있겠습니다.

삽입: O(log n)
삭제(최우선순위 요소 추출): O(log n)
최우선순위 요소 확인(삭제 없이): O(1) - 힙에서 루트 요소 확인.

6. 우선순위 큐 우선순위 부여 방식

마지막으로 우선순위 큐의 우선순위 부여 방식에 대해 살펴봅쉬다.

1)정수 기반 우선순위

일반적으로 숫자를 사용하여 우선순위를 나타냄.
예: 숫자가 작을수록 높은 우선순위 (1: 최고, 2: 중간, 3: 낮음).

2)튜플 기반 우선순위

복합적인 우선순위 기준이 필요할 경우, 튜플을 사용.
예: (우선순위, 삽입순서) 형태로 구성하여 동일한 우선순위에서는 삽입 순서에 따라 처리.

pq.push((priority, order), value)

3)커스텀 우선순위

객체에 우선순위를 정의하거나, 조건에 따라 정렬 기준을 설정.

class Task:
    def __init__(self, priority, name):
        self.priority = priority
        self.name = name

    def __lt__(self, other):
        return self.priority < other.priority

# Task 객체를 힙에 삽입
heapq.heappush(pq.heap, Task(1, "Task 1"))

이상으로 오늘은 우선순위 큐에 대해서 알아보았는데요.

제가 공부하다가 헷갈렸던 부분 위주로 정리했는데, 우선순위 큐 개념이 헷갈리시는 분들에게 도움이 되었으면 좋겠습니다.

감사합니다.