우선순위 큐
선입선출의 자료구조인 큐와는 다르게 우선순위가 높은 데이터가 큐에서 먼저 빠져 나오게 된다. 우선순위 큐를 구현하는 방법은 총 3가지가 있다.
1. 배열을 기반으로 구현.
단점 :
1. 데이터 삽입 및 삭제에서 데이터를 한칸씩 밀고 당기기를 해야 해서 효율이 좋지 못하다.
2. 삽입할 위치를 찾을 땐 우선순위를 전부 비교해야 하기 때문에 또 배열 전체를 뒤져야 함.
2. 연결리스트를 기반으로 구현.
단점 :
1. 배열기반 구현의 1번 단점은 없지만, 배열과 마찬가지로 위치를 찾아야 해서 우선순위를 전부 비교해야 한다.
3. 힙을 이용하여 구현.
위와 같은 이유로 우선순위 큐는 힙을 이용해서 구현한다.
