우선순위 큐(면접을 위한 CS 전공지식 노트)

우선순위 큐

우선순위 큐

우선순위 큐(Priority Queue)는 비선별형 자료구조로, 

요소들을 저장하고 검색하는 일반적인 큐(Queue)와는 다르게 각 요소가 우선순위를 가지고 있습니다. 

이것은 일반적으로 요소를 우선순위에 따라 정렬된 순서로 처리하거나 접근하기 위해 사용됩니다. 

 

작업 스케줄링: 

우선순위 큐를 사용하여 다양한 작업 또는 태스크를 우선순위에 따라 처리하는 스케줄링 

알고리즘을 구현할 수 있습니다. 

높은 우선순위를 가진 작업이 낮은 우선순위를 가진 작업보다 먼저 실행됩니다.

그래프 알고리즘: 

다익스트라 알고리즘, A* 알고리즘 및 프림 알고리즘과 같은 그래프 기반 알고리즘에서 최소 거리나 

최소 비용 경로를 찾을 때 우선순위 큐가 사용됩니다.

이벤트 처리: 

이벤트 처리 시스템에서 다음 이벤트를 처리하기 위해 우선순위에 따라 이벤트를 정렬하는 데 사용됩니다.

데이터 압축 및 압축 해제: 

우선순위 큐를 사용하여 데이터의 압축 또는 압축 해제 작업 중에 바이트 또는 

기호를 처리하는 데 유용합니다.

 

큐의 연산

삽입(Insertion): 

요소를 우선순위 큐에 추가합니다. 

이 때, 각 요소는 특정 우선순위를 갖게 됩니다.

추출(Extraction): 

가장 높은 우선순위를 가진 요소를 큐에서 제거하고 반환합니다. 

이 작업은 "최빈원 요소(peek)"를 구현하는 것과 동일합니다.

우선순위 큐는 다양한 방식으로 구현될 수 있습니다. 

일반적인 구현 방법으로는 이진 힙(Binary Heap), 이진 검색 트리(Binary Search Tree), 

Fibonacci 힙(Fibonacci Heap) 등이 있습니다. 

각 구현 방식은 성능과 사용 사례에 따라 다른 장단점을 가집니다.

우선순위 큐의 중요한 특성 중 하나는 요소의 우선순위를 비교하여 정렬하기 때문에 

비선별형 자료구조라고 할 수 있습니다. 

이는 다른 큐와 달리 요소들의 순서가 추가된 순서나 FIFO(선입선출)와 관련이 없고, 

요소의 우선순위에 따라서만 정렬됩니다.

 

우선순위 큐 자세히 알기!!

상상해보세요, 당신이 할 일 목록을 관리하는 프로그램을 만들고 있다고 가정해봅시다. 

이 목록에는 다양한 작업이 들어 있습니다. 

어떤 작업은 급한 상황에서 해결해야 하고, 다른 작업은 조금 더 나중에 해도 괜찮은 것들일 수 있습니다.

이때, 이 할 일 목록을 우선순위 큐로 관리하면 어떨까요? 

각 작업은 우선순위를 가지며, 높은 우선순위를 가진 작업은 더 중요한 작업을 나타냅니다.

예시:
"급한 이메일 회신" - 높은 우선순위
"빨래 세탁" - 중간 우선순위
"책 읽기" - 낮은 우선순위
이제 우선순위 큐에 이 작업들을 추가하면, 큐는 우선순위에 따라 다음과 같이 정렬됩니다.

"급한 이메일 회신"
"빨래 세탁"
"책 읽기"
이 상태에서 작업을 추출할 때, 가장 높은 우선순위를 가진 작업부터 처리됩니다. 

따라서 "급한 이메일 회신"이 가장 먼저 처리됩니다.

이와 같이 우선순위 큐는 작업을 우선순위에 따라 관리하고 처리할 때 사용되는 자료구조입니다. 

이것은 작업 관리 외에도 다양한 응용 분야에서 활용되며, 

요소들을 우선순위에 따라 정렬하는 데 사용됩니다.