> For the complete documentation index, see [llms.txt](https://dahye-jeong.gitbook.io/til/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dahye-jeong.gitbook.io/til/algorithm/2018-06-02-algorithm-pqueue.md).

# Priority Queue

| 자료구조                                                                     | 처리순서                      |
| ------------------------------------------------------------------------ | ------------------------- |
| [Stack](https://dh00023.github.io/algorithm/ds/2018/04/24/algorithm-9/)  | LIFO : 나중에 들어온 데이터가 먼저 처리 |
| [Queue](https://dh00023.github.io/algorithm/ds/2018/04/25/algorithm-10/) | FIFO : 먼저 들어온 데이터가 먼저 처리  |
| **Priority Queue**                                                       | 우선순위가 높은 데이터가 먼저 처리       |

우선순위 큐는 들어간 순서에 상관없이 **우선순위가 높은** 데이터가 먼저나온다.

* 시뮬레이션 시스템 (ex) 출발시간, 대기시간, 소요시간
* 네트워크 트래픽 제어
* 운영 체제에서의 작업 스케쥴링

데이터를 근거로 우선순위를 판단해야하며, 목적에 맞게 우선순위를 정해야한다. 우선순위가 같은 데이터도 존재할 수 있다.

우선순위 큐에서 가장 중요한 연산은 **삽입(insert)과 삭제(delete)**이다.

| 연산           | 설명                              |
| ------------ | ------------------------------- |
| create()     | 우선순위 큐를 생성                      |
| init(q)      | 우선순위 큐 q 초기화                    |
| is\_empty(q) | 우선순위 큐 q가 비어있는지 검사              |
| is\_full(q)  | 우선순위 큐 q가 가득찼는지 검사              |
| insert(q,x)  | 우선순위 큐 q에 x추가                   |
| delete(q)    | 우선 순위큐로부터 가장 우선순위가 높은 요소 삭제, 반환 |
| find(q)      | 우선순위가 가장 높은 요소 반환               |

## 구현방법

우선순위 큐는 3가지 방법으로 구현할 수 있다.

1. 배열을 기반으로 구현
2. 연결리스트를 기반으로 구현
3. **힙(Heap)을 이용하는 방법**

### 배열과 연결리스트

[배열](https://dh00023.github.io/algorithm/ds/2018/04/21/algorithm-5/)이나 [연결리스트](https://dh00023.github.io/algorithm/ds/2018/04/23/algorithm-8/)를 이용해서 구현하면 힙보다는 간단하게 구현할 수 있으나 단점이 있다.

#### 배열

* 데이터 삽입 및 삭제에서 데이터를 이동하는 연산을 계속해야한다. (당기거나 밀어야하는)
* 삽입 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위를 비교해야한다.

#### 연결리스트

* 삽입 위치를 찾기위해서 모든 노드에 저장된 데이터와 우선순위를 비교해야한다.

데이터가 적은 경우에는 단점이 아닐 수도 있지만 데이터가 많아지면 비교할 대상이 많아져 성능이 저하된다.

#### [힙(Heap)](https://dh00023.github.io/algorithm/ds/2018/06/02/algorithm-heap/)

* 힙은 완전이진트리로 구현한다. 힙에 대한 자세한 설명은 힙(Heap) 게시물에서 했다.

| 표현방법        | 삽입      | 삭제      |
| ----------- | ------- | ------- |
| 순서없는 배열     | O(1)    | O(n)    |
| 순서없는 연결 리스트 | O(1)    | O(n)    |
| 정렬된 배열      | O(n)    | O(1)    |
| 정렬된 연결리스트   | O(n)    | O(1)    |
| 힙(Heap)     | O(logn) | O(logn) |

이러한 성능차이로 주로 Heap을 이용해서 우선순위큐를 구현하는 것이 일반적이다.