우선순위 큐(Priority Queue)

1. 우선 순위 큐

- 큐에 넣을 데이터들이 우선 순위가 있다.

- 우선 순위가 높은 것부터 꺼낼 수 있도록 한다.

 

2. 구현 방법

1. 배열

배열로 구현할 때, 우선순위가 높을수록 배열의 앞에 위치시키며 아래와 같은 단점이 있다.

 

1) 데이터를 삽입 및 삭제할 때, 데이터를 한 칸씩 밀고 당겨야 한다. => 연산 증가

2) 삽입 위치를 찾기 위해 처음부터 하나씩 비교를 해야 한다.

 

2. 연결 리스트

연결 리스트로 구현할 때, 배열과 마찬가지로 우선순위가 높을수록  리스트 앞쪽에 위치시킨다.

배열의 첫 번째 단점은 없지만, 두 번째 단점은 여전히 존재한다.  따라서 우선순위 큐는 힙을 사용하는 경우가 많다.

 

3. 힙

힙은 우선순위를 고려한 '완전 이진 트리'이다.

*완전 이진 트리 : 자식 subtree가 최대 2개, 위에서 아래로 & 왼쪽에서 오른쪽 순서대로 모두 채워져야 한다.

 

최대 힙(max heap)은 루트 노드로 올라갈수록 데이터가 커지는 완전 이진 트리를 말한다. 즉, 값이 큰 것이 우선 순위가 높다고 보는 것이다.

반대로, 최소 힙(min heap)은 루트 노드로 올라갈수록 데이터가 작아지는 완전 이진 트리를 말한다.

 

1) 삽입

'3'을 추가한다고 할 때, 먼저 트리의 마지막 부분에 추가합니다.

그다음, 부모의 값과 비교해서 자신의 우선순위가 더 높으면 교체하면서 올라갑니다.

 

2) 삭제

 

힙에서 root노드의 데이터를 꺼낸다.

그리고 마지막 노드를 루트 노드 자리로 옮기고, 자식 노드 중 우선 순위가 더 높은 값과 비교해서 교체해나간다.