우선순위큐

큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오나 우선순위 큐는 다르다.

들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

우선순위 큐를 구현하는 방법 3가지

1. 배열을 기반으로 구현하는 방법

2. 연결리스트를 기반으로 구현하는 방법

3. 힙(Heap)을 이용하는 방법

배열을 사용하는 경우 단점

- 데이터 삽입 및 삭제과정에서 데이터를 한 칸씩 당기거나 밀어야 하는 연산을 계속 하여야 한다.

- 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다.

이 경우 우선순위가 가장 낮은 데이터를 저장하는 경우에 발생할 최악의 경우임

연결리스트를 사용하는 경우 단점

- 삽입의 위치를 찾기 위해 첫번째 노드에서부터 시작해 마지막 노드에 저장된 데이터와 우선순위를 비료를 진행할지도 모른다.

이 경우 데이터가 많아질 때 노드의 수에 비례해서 비교할 대상이 증가하므로 성능이 저하된다.

그래서 우선순위 큐는 주로 힙(Heap)을 이용해서 구현하는 것이 일반적이다.

힙의 구현 - 최소 힙 기준

2를 추가할때 

힙 삭제 시 

맨 위의 데이터를 먼저 지운다.