목차

• 우선순위 큐의 개념
• 우선순위 큐의 구현 방법
• 우선순위 큐의 활용 예시

우선순위 큐(Priority Queue)란?

우선순위 큐는 데이터를 저장하고 있는 자료구조 중 하나로, 각 요소에 우선순위를 부여하여 우선순위가 높은 요소가 먼저 처리되는 구조를 갖는다.
일반적인 큐(Queue)와는 달리, 데이터가 들어온 순서가 아니라 우선순위에 따라 처리된다.

우선순위 큐의 개념

우선순위 큐는 일반적으로 두 가지 주요 연산을 지원한다.

• 삽입(Insertion): 요소를 큐에 추가합니다. 이때 각 요소는 우선순위를 가지고 있다.
• 삭제(Deletion): 가장 높은 우선순위를 가진 요소를 큐에서 제거하고 반환한다.

우선순위 큐의 구현 방법

배열(Array)을 이용한 구현

가장 간단한 방법 중 하나는 배열을 사용하여 우선순위 큐를 구현하는것! 이때 각 요소는 우선순위와 함께 저장되고, 삽입과 삭제 연산 시에 우선순위에 맞게 요소를 삽입하거나 삭제한다.

class PriorityQueueArray:
    def __init__(self):
        self.queue = []

    def push(self, item, priority):
        self.queue.append((item, priority))

    def pop(self):
        if not self.is_empty():
            highest_priority_index = 0
            for i in range(1, len(self.queue)):
                if self.queue[i][1] < self.queue[highest_priority_index][1]:
                    highest_priority_index = i
            return self.queue.pop(highest_priority_index)[0]
        else:
            return None

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

# 우선순위 큐 배열 구현 사용 예시
pq_array = PriorityQueueArray()
pq_array.push('task1', 3)
pq_array.push('task2', 1)
pq_array.push('task3', 2)

while not pq_array.is_empty():
    print(pq_array.pop())  # 출력: task2 -> task3 -> task1

힙(Heap)을 이용한 구현

힙은 이진트리의 일종으로, 우선순위 큐를 구현하는 데 효율적으로 사용될 수 있다. 일반적으로 최대 힙 또는 최소 힙을 사용하여 우선순위 큐를 구현하며, 이를 통해 삽입과 삭제 연산을 O(log n)의 시간복잡도로 수행할 수 있다.

import heapq

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

    def push(self, item, priority):
        heapq.heappush(self.heap, (priority, item))

    def pop(self):
        if not self.is_empty():
            return heapq.heappop(self.heap)[1]
        else:
            return None

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

# 우선순위 큐 힙 구현 사용 예시
pq_heap = PriorityQueueHeap()
pq_heap.push('task1', 3)
pq_heap.push('task2', 1)
pq_heap.push('task3', 2)

while not pq_heap.is_empty():
    print(pq_heap.pop())  # 출력: task2 -> task3 -> task1

우선순위 큐의 활용 예시

의료 분야

의료 분야에서는 환자의 상태에 따라 치료 우선순위를 정하는 데 우선순위 큐가 활용될 수 있다.
응급 환자나 중증 환자는 더 높은 우선순위를 가지고, 이에 따라 진료 및 치료 순서가 결정된다!

작업 스케줄링

운영체제에서는 다양한 프로세스나 작업들을 스케줄링하는 데 우선순위 큐를 사용할 수 있다.
각 작업에는 실행 우선순위가 부여되어 있고, 이를 기준으로 스케줄링이 이루어진다!