[Priority Queue]26. Priority Queue(우선순위 큐)

목차

1. Priority Queue ADT(우선순위 큐)

2. minPQ, maxPQ

 

1. Priority Queue ADT(우선순위 큐)

 

1) 특징

- Priority Queue ADT(우선순위 큐)는 queue의 성질을 따르지만, 필요한, 그리고 중요한 내용을 먼저 꺼내는 방식을 말합니다.

 

2) 주요 기능

- insert(e): e라는 element를 insert하는 함수

- removeMin(): 가장 작은 key를 지닌 값을 제거하는 함수

 

3) 부가 기능

- min(): 가장 작은 key를 지닌 값을 반환, 제거하지는 않는다

- size(), empty()

 

2. minPQ, maxPQ

 Priority Queue는 크게 2가지로 나뉘는데, minPQ와 maxPQ로 나뉘어집니다. 이름에서 추측할 수 있듯이, minPQ는 최소 우선순위 큐, maxPQ는 최대 우선순위 큐를 의미합니다. 위의 기능들은 minPQ일 경우을 가정하고 적어놓은 함수들이며, 만일에 maxPQ라면 removeMin(), min()함수가 각각 removeMax(), max()으로 교체되었을 것 입니다.