우선순위 큐란?
정의
•
각 요소가 우선순위를 가지며, 우선순위가 높은 요소가 먼저 나가는 자료구조
•
우선순위에 따라 처리 순서가 결정되는 추상 자료형
특징
•
선입선출(FIFO - First In First Out) 구조인 일반 큐와는 달리, 요소의 우선 순위에 따라 처리 순서가 달라진다.
◦
4 → 8 → 3 순으로 데이터가 들어간다고 했을 때 큐와 우선순위 큐의 처리순서는 다음과 같다. (높은 값이 높은 우선순위를 갖는다고 가정)
▪
input : 4 → 8 → 3
▪
큐 : 4 → 8 → 3
▪
우선순위 큐 : 8 → 4 → 3
•
내부적으로 다양한 자료구조(힙, 연결 리스트, 배열)를 사용하여 구현될 수 있으나 효울성을 위해 주로 힙을 사용한다.
◦
배열 기반 구현
▪
삽입은 빠르나 최우선 요소를 찾는 데에는 시간이 많이 걸린다.
◦
연결 리스트 기반 구현
▪
최우선 요소를 쉽게 찾을 수 있으나 삽입과 제거에 더 많은 시간이 소요될 수 있다.
◦
힙 기반 구현
▪
최우선 요소의 삽입과 제거 모두에 효율적이다.
▪
힙 방식이 최악에 경우라도 O(logN)을 보장하기 때문에 일반적으로 힙으로 구현한다.
기본 동작
※ 값이 클수록 우선순위가 높다고 가정 (최대 힙)
•
peek()
◦
우선순위 큐에서 최대 우선순위 값을 반환한다.
◦
최대 우선순위 값(최대 힙)은 항상 루트에 있으므로 루트 값을 반환한다.
•
enqueue()
◦
우선순위 큐(최대 힙)에 요소를 삽입하는 작업을 한다.
◦
삽입 작업은 다음과 같다.
1.
힙 끝에 새 요소를 삽입
2.
부모 노드와 비교하여 힙 속성을 위배하는 경우 부모 노드와 값을 바꾼다.
3.
힙 속성이 유지될 때까지 2번 작업을 반복
•
heapify()
◦
힙 속성을 유지하는 작업을 한다.
◦
위에서 아래로 내려가면서 작업을 한다.
◦
max heap에서 heapify의 작업은 다음과 같다.
1.
자식 노드와 우선순위를 비교
2.
만약 자식 노드 우선순위가 높다면 왼쪽 오른쪽 자식 중 우선순위가 높은 노드와 교환
3.
힙 속성이 유지될 때까지 1,2번 과정을 반복
•
dequeue() - queue에서 최대 우선 순위 요소를 삭제하고 그 값을 반환한다.
◦
우선순위 큐(최대 힙)에 최대 우선순위 요소를 삭제하고 그 값을 반환하는 작업을 한다.
◦
삭제 작업은 다음과 같다.
1.
루트 노드의 값을 추출한다.
2.
heap 마지막 요소를 루트 노드에 배치한다.
3.
마지막 요소는 제거한다.
4.
루트 노드부터 heapify를 수행한다.
사용 사례
•
네트워크 트래픽 제어
◦
데이터 패킷의 우선순위를 관리하여 중요한 정보를 먼저 전송한다.
•
운영체제의 스케쥴링
◦
프로세스 또는 스레드에 우선순위를 부여하여 시스템 자원을 효율적으로 관리한다.
•
경로 찾기 알고리즘
◦
에이스타(A*) 알고리즘은 그래프 상 두 점 사이의 최단 경로를 찾는 데 사용되는 대표적인 경로 찾기 알고리즘이다.
◦
우선순위 큐를 사용하여 다음에 탐색할 노드를 결정한다.
◦
각 노드는 시작점부터 해당 노드까지의 거리와 목표점까지의 예상 거리를 기반으로 우선순위가 계산되며, 우선순위가 높은 노드(즉, 목표점에 더 가까울 것으로 예상되는 노드)부터 탐색한다.
◦
이 방법으로 불필요한 경로 탐색을 최소화하고 효율적으로 최단 경로를 찾을 수 있다.
