우선순위 큐(Priority Queue)

목차

1. 우선순위 큐 란?
2. 큐와의 차이점
3. 우선순위 큐의 사용 예시

1. 우선순위 큐 란?

우선순위 큐란 기존의 큐에 우선순위 개념을 더해준 자료구조입니다.
큐에 저장된 자료들은 각각의 우선순위에 따라 정렬됩니다.

2. 큐와의 차이점

큐와의 차이점을 보여드리기위해 실제로 push하는 장면을 보여드리겠습니다.

우선순위 큐의 우선순위는 큰 숫자의 기준이며 각각 2, 1, 3, 5, 4의 순서대로 push를 진행하도록 하겠습니다.

위에서 과정에서 볼 수 있듯이 우선순위 큐에서는 배열에 추가될 경우에 순서대로 입력되는 것이 아닙니다.

앞서 말씀드렸듯 우선순위 큐의 우선순위를 "큰 숫자"로 지정했기 때문에 새로운 자료가 입력될 때마다 기존에 입력된 자료보다 "큰 숫자"인지를 비교하며 배열에 자리잡습니다.
위 과정중 push(4)를 진행하는 부분으로 예시를 들어보겠습니다.

3. 우선순위 큐의 활용

우선 배열의 순서 자체를 다시 정렬하는 과정이 필요하기 때문에 다른 자료구조 및 알고리즘들과 함께 사용되는 경우가 많습니다.
우선순위 큐가 필요한 경우는 크게 두가지 전제조건을 가진 상황이라고 생각하면 좋습니다.
1. 과정 중 자료를 특정 기준으로 정렬해야 한다. = 자료를 정렬한 기준이 존재한다.
2. 순자적으로 정렬된 자료를 한 쪽 끝에서 사용, 삭제해야 한다.