우선순위 큐 편집하기

'''우선순위 큐'''(priority queue)는 일반적인 큐와 달리, 삽입된 요소 중 우선순위(priority)가 가장 높은 요소를 먼저 꺼내는 자료 구조이다. 기본적인 큐의 선입선출(FIFO) 원칙을 따르지 않고, 우선순위에 따라 데이터를 처리한다.
==개요==
우선순위 큐는 각 요소에 우선순위를 부여하여, 데이터가 삽입된 순서와 무관하게 우선순위가 높은 데이터가 먼저 처리되도록 한다. 일반적으로 최소 힙(min-heap) 또는 최대 힙(max-heap) 자료 구조를 이용해 구현된다.
==주요 연산==
*'''삽입(Enqueue)'''
**새 요소를 우선순위와 함께 큐에 추가한다.
*'''삭제(Dequeue)'''
**우선순위가 가장 높은(또는 가장 낮은) 요소를 큐에서 제거하고 반환한다.
*'''Peek'''
**큐에서 우선순위가 가장 높은 요소를 제거하지 않고 확인한다.
==특징==
*선입선출(FIFO) 대신 '''우선순위순'''으로 요소를 처리한다.
*삽입과 삭제 연산은 힙(Heap) 자료 구조를 이용하면 효율적으로 O(log n)에 수행할 수 있다.
*일반 배열이나 정렬된 리스트로도 구현할 수 있으나, 힙을 이용하는 것이 성능 면에서 우수하다.
==구현 방법==
*'''배열 기반'''
**삽입 시 단순 추가하고, 삭제 시 가장 높은 우선순위를 선형 탐색하여 제거 (비효율적).
*'''정렬된 배열/리스트'''
**삽입 시 정렬을 유지하여 추가, 삭제는 맨 앞 요소를 제거.
*'''힙(Heap) 구조'''
**삽입과 삭제 모두 O(log n) 시간 복잡도로 처리할 수 있어 가장 일반적이다.
==활용 예시==
*작업 스케줄링(높은 우선순위 작업을 먼저 처리)
*네트워크 패킷 우선 전송
*다익스트라 알고리즘(최단 경로 탐색)
*이벤트 기반 시뮬레이션
==간단한 구현 예시==
<syntaxhighlight lang="python">
import heapq

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

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

    def dequeue(self):
        if self.heap:
            return heapq.heappop(self.heap)[1]
        raise IndexError("dequeue from empty priority queue")

    def peek(self):
        if self.heap:
            return self.heap[0][1]
        raise IndexError("peek from empty priority queue")

# 사용 예시
pq = PriorityQueue()
pq.enqueue(2, "Task A")
pq.enqueue(1, "Task B")
pq.enqueue(3, "Task C")

print(pq.dequeue())  # 출력: Task B (우선순위 1)
print(pq.dequeue())  # 출력: Task A (우선순위 2)
</syntaxhighlight>
==우선순위 큐와 일반 큐의 차이==
*'''일반 큐''': 삽입 순서대로 요소를 처리 (FIFO).
*'''우선순위 큐''': 우선순위가 높은 요소를 먼저 처리.
==같이 보기==
*[[힙]]
*[[큐]]
*[[다익스트라 알고리즘]]
*[[힙 정렬]]
==참고 문헌==
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). ''Introduction to Algorithms'' (3rd ed.). MIT Press.
*Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). ''Data Structures and Algorithms in Java'' (6th ed.). Wiley.
[[분류:자료 구조]]