[C++] 우선순위 큐

📕 우선순위 큐(priority queue)

• FIFO, LIFO가 아닌 규칙을 정해서 꺼냄.
• 우선순위 규의 기본 규칙은 "큰 숫자 우선"
• complete binary tree(힙 구조)
  -> 반복횟수(노드 추가) : 1
• 직접 연결된 node에서 부모가 자식보다 우선순위가 높다.
  -> 반복횟수(data개수: N) : 트리의 높이를 의미
  -> 최악의 경우 : 그래프의 높이랑 일치
  -> 부모의 노드는 N/2 -> 맨 위까지 가면 N/2/2/2/.... = 1
  -> logN

사용 방법

#include <queue>

priority_queue<int> pq;

pq.top() = 우선순위가 가장 높은 데이터 반환
pq.pop() = 우선순위가 가장 높은 데이터 삭제

우선순위(전략)

• 내가 어떤 순서로 data를 처리할 것인가.

complete binary tree

• 트린데 자식이 2개를 넘지 않는다
• node를 추가하는 순서가 정해져있다.
  -> 제일 왼쪽부터 채워진다.

---

노드 추가

1. complete binary tree에 따라 왼쪽부터 채우고
2. 추가된 노드의 부모의 우선순위를 비교하여 swap한다.

시간복잡도(추가)

추가하고 우선순위를 갱신해야한다.
1개 추가 logN, N개 추가 NlogN

노드 삭제

1. complete binary tree 규칙에 맞춰 최하단 우측과 바꿔주고 꺼낸다.
2. 내려올 때 어디쪽으로 내려가야할까?
   -> 자식 2개에서 우선순위가 높은쪽으로~
3. 2번 반복...

시간복잡도(삭제)

1. complete binary tree => 1
2. 부모가 자식보다 우선순위가 높다.
   -> 최악: 맨위에서 맨 밑으로 내려오는 경우(그래프 높이)
   -> logN

---

📒 Sort vs 우선순위 큐

기본상황 : N개의 data

시간복잡도

sort: NlogN
우선순위 큐: NlogN
비슷해 보이지만 차이가 있다.
추가상황: 1개의 data를 추가적으로 넣고 처리 과정을 M번 반복
sort: M*(N+M)log(N+M)
우선순위 큐: Mlog(N+M)

사용

sort는 data가 고정된 경우(n번째로 큰수 찾을때 sort[n])
index로 바로 접근가능할 때 유리하다.

우선순위 큐는 data가 변경될 때