우선순위 큐(Priority Queue)

우선순위 큐는 key, value로 이루어진 pair를 저장하는 비선형 자료구조이다.

여기서 key는 데이터의 priority를 뜻한다.

스택은 가장 최근에 들어온 데이터, 큐는 가장 먼저 들어온 데이터가 삭제되지만

우선순위 큐는 삽입된 순서와 상관없이 우선순위가 높은 데이터가 먼저 삭제된다.

따라서 우선순위 큐에는 정렬이 필요하다.

우선순위 큐를 구현하는 방법은 배열, 링크드리스트, 힙을 이용하여 구현한다.

배열

배열을 이용하여 구현시 삽입되는 위치를 찾아야 하기 때문에 기존에 저장된 데이터와 우선순위를 비교해주어야 하는 문제점이 생기고 최악의 경우에 기존에 있는 모든 데이터와 비교해야 할 수도 있다.

또한 삽입, 삭제 시 기존의 데이터를 밀고 당기는 연산을 계속해야 하는 추가적인 문제가 생긴다.

링크드리스트

링크드리스트를 이용할 때 삽입 삭제 시 앞 뒤 노드의 포인터만 연결해주면 되므로 배열에서 나타난 데이터를 밀고 당겨야 하는 문제는 없다.

하지만 데이터 삽입 시 삽입되는 위치를 찾아야 하기 때문에 기존 데이터와 우선순위를 비교해야 하고 최악의 경우에 모든 데이터와 비교해야 하는 문제가 생길 수 있다. 이러한 문제는 데이터가 많지 않을 때 큰 문제가 되지 않지만 데이터가 많을 수록 비교해야 하는 연산이 증가하므로 그만큼 성능이 저하될 수 있다.

힙

힙은 완전이진트리(자식 노드가 최대 2개이며, height-1은 포화이진트리, 최대 height에선 왼쪽부터 오른쪽으로 삽입됨)를 사용하므로 이를 이용해 우선순위 큐를 이용하는 것이 효과적이다.

min-heap, max-heap으로 나눌 수 있으며 min-heap은 부모노드가 자식노드보다 작은 heap이다. 여기서 부모와 자식관계만 따지고 형제들끼리 비교하진 않는다. 

max-heap은 min-heap의 반대

key값이 작을 수록 우선순위가 높다고 가정할 것이기 때문에 min-heap을 통해 삽입, 삭제 시 어떻게 변화하는지 알아보자. 

삽입

1. 데이터를 삽입할 땐 마지막 위치인 최대 depth의 가장 오른쪽에 삽입한다.

2. 새로 삽입된 데이터의 우선순위를 자신의 부모와 비교하여 위치를 바꿔준다.

밑에서 삽입하고 parent와 비교 후 교체한다.

삭제

우선순위 큐에서 삭제는 우선순위가 가장 높은 것을 삭제하기 때문에 그냥 root를 삭제하면 된다.

그리고 root의 자리가 채워지도록 정렬하면 된다.

1. root를 삭제한다.

2. 가장 마지막 노드를 root로 올린다.

3. 2개의 자식 노드 중 우선순위가 높은 자식노드와 교환한다.

4. 제자리를 찾을 때까지 3을 반복한다.

힙은 height가 log n이므로 Up-heap과 Down-heap이 O(log n) time에 수행된다. (밑이 2)