우선순위 큐(Prioriy Queue)

📌 우선순위 큐란?

FIFO 형식의 큐와 달리 들어오는 순서에 상관없이 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

 

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

• 배열로 구현
• 연결리스트로 구현
• 힙(Heap)을 이용

 

1) 배열 및 연결리스트

배열이나 연결리스트를 이용해서 우선 순위 큐를 구현하는 경우 간단하게 구현이 가능하다는 장점이 있다.

하지만 배열의 경우에는 여러가지 단점이 존재한다.

• 데이터 삽입 및 삭제 과정에서 데이터를 한 칸씩 당기거나 밀어야하는 연산을 계속해야 한다.
• 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다.

 

2) 힙

배열의 shift 연산, 연결리스트의 삭제 및 삽입 하는 경우 순회하는 시간복잡도에 비해 힙을 통한 삽입 삭제는 부모와 자식 간에만 비교 하기 때문에 시간 복잡도 O(NlogN) 으로 해결 할 수 있다.

힙의 특성상 부모와 자식의 간의 비교를 통해서 우선 순위를 나누고 힙 정렬을 통해 지속적으로 정리 해준다. 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한다.

1. 힙이란?

힙(Heap)이란 완전 이진트리 형태의 자료구조로 힙 조건을 만족한다. 일차원 배열로 구현할 수 있고 일반적으로 그룹을 정렬하거나 입력된 데이터 안에서 최소/최대 값을 찾을 때 사용한다. 데이터의 삽입과 삭제가 빠르며 각각의 수행시간이 O(logN)이다.

 

2. 최소 힙과 최대 힙

1) 최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

2) 최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

* 완전 이진트리 : 마지막 레벨을 제외하곤 완전히 꽉 찬 상태이고, 마지막 레벨의 맨 왼쪽부터 꽉 차 있어야함.

 

3. 힙의 구현

1) 힙의 삽입 연산

① 트리의 가장 마지막 위치에 노드를 삽입한다.

② 추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인한다.

③ 만족하지 않는다면 부모와 자식의 키 값을 바꾼다.

④ 조건에 만족하거나 추가된 노드가 루트에 도달할 때 까지 2~3을 반복한다.

 

2) 힙의 삭제 연산

① 힙의 삭제 연산은 항상 루트 노드를 삭제한다.

② 트리의 가장 마지막 노드를 루트 자리로 삽입한다.

③ 바꾼 위치의 노드가 힙 조건을 만족하는지 확인한다.

④ 만족하지 않는다면 왼쪽 자식과 오른쪽 자식 중 적합한 노드와 키 값을 바꾼다.

⑤ 조건을 만족하거나 리프 노드에 도달할 때 까지 3~4를 반복한다.

 

📃 우선순위 큐 사용법

- 선언

// 낮은 숫자가 우선 순위인 int 형 우선순위 큐
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

// 높은 숫자가 우선 순위인 int 형 우선순위 큐
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

만약 따로 우선순위 옵션을 주고 싶다면 Compartor을 통해서 구현하면된다.

 

- 삽입

priorityQueue.add(1); //삽입에 성공하면 true를 반환하고, 실패한다면 IllegalStateException를 반환
priorityQueue.offer(2);

우선순위 큐에 값을 삽입하면, 그와 동시에 내부 힙을 통해서 부모와 자식간의 값을 비교해서 우선순위가 높은 순으로 정렬한다.

 

- 삭제

// 큐에서 우선순위에 따라 정렬된 값중 가장 첫번째 값을 반환함과 동시에 큐에서 제거한다. 
// 만약 큐가 비어있다면 null을 반환한다.
priorityQueue.poll(); 

// 큐에서 가장 첫번째 값을 제거한다.
priorityQueue.remove();

// 큐를 비운다.
priorityQueue.clear();

 

- 출력

priorityQueue.peek();

 

 

[참고]

https://velog.io/@jangwonyoon

우선 순위 큐는 어떻게 작동하는 가?

https://velog.io/@namkun

Priority Queue(우선순위 큐)