Priority Queue

📖Queue

📖Priority Queue

일반 queue처럼 FIFO 형식이 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조

📖특징

• 모든 값은 우선순위가 존재
• 우선순위가 높은 값이 먼저 나가는 형태
• Heap으로 구현 시 O(logn)을 보장하기 때문에, 일반적으로 Heap을 통해 구현
• 우선순위가 같은 값이 있다면 queue의 순서에 따라 먼저 나감

📖연산

• enqueue((k, v)) : 우선순위 큐에 데이터 삽입
• dequeue() : 우선순위 큐에서 우선순위가 높은 데이터를 삭제하고 return
• isEmpty() : 우선순위 큐에 데이터가 없으면 True, 있으면 False return
• size() : 우선순위 큐에 있는 데이터의 개수를 return
• peek() : 우선순위 큐에서 우선순위가 가장 큰 값을 return

📖사용

• CPU 스케줄링
• 다익스트라 알고리즘

📖시간복잡도

구현 방법	enqueue()	dequeue()
Unsorted Array	O(1)	O(n)
Unsorted Linked List	O(1)	O(n)
Sorted Array	O(n)	O(1)
Sorted Linked List	O(n)	O(1)
Heap	O(logn)	O(logn)