지금까지는 선입선출의 큐를 알아보았다.

우선순위 큐는 데이터 원소들 각각이 우선순위가 정해져 있고, 그 우선순위에 따라 큐에서 빠져나온다.

• 작은 수가 우선순위가 높다고 가정
• 예) Enqueue: 6, 7, 3, 2
• Dequeue: 2, 3, 6, 7
• 현재 큐의 원소중에 우선순위가 높은 원소가 먼저 나온다.

우선순위 큐의 활용

운영체제의 CPU 스케줄러 등

우선순위 큐의 구현

서로 다른 두 가지 방식이 가능하다.

1. Enqueue 할 때 우선순위 순서를 유지하도록
2. Dequeue 할 때 우선순위 높은 것을 선택

어느 것이 더 유리할까?

• 1번이 조금 더 유리하다
• 큐에 원소들이 들어온 순서대로 (우선순위를 기준으로 정렬되어 있지 않고) 들어가 있다면, Dequeue 할 때 우선순위가 높은 것을 선택하기 위해 모든 원소를 탐색해야 한다 —> O(n)
• Enqueue 할 때 우선순위를 유지하면 큐의 길이에 비례하는 복잡도는 맞지만, 모든 원소를 찾아볼 필요는 없다.