[자료구조] 우선순위 큐 (Priority Queue)

1. 우선순위 큐란 무엇인가

---

큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 FIFO (First In First Out) 구조를 가진다. 여기서 FIFO 구조란 먼저 들어온 데이터가 먼저 나가는 구조이다. 우선순위 큐(Priority Queue)는 먼저 들어온 순서대로 데이터가 나가는 것이 아니라 우선순위를 먼저 결정하고 우선순위가 높은 element가 먼저 나가는 자료구조이다. 우선순위 큐는 힙(Heap)을 이용하여 구현하는 것이 일반적이다.

 

 

(1) 우선순위 큐의 특징

• 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조 ( 우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야 한다.)
• 내부구조가 힙으로 구성되어 있으므로 시간 복잡도는 O(NLogN) 이고, 이진트리 구조로 이루어져 있다. 
  • 힙
    • 동적으로 변하는 데이터에서 최댓값과 최솟값을 빠르게 찾기 위한 완전 이진트리 자료구조
    • 시간복잡도 : O(log N)
    • 최대힙 : 부모노드 값이 자식노드의 값보다 큰 형태로 만들어지는 완전 이진 트리, 루트노드에 항상 가장 큰 값 존재
    • 최소힙 : 부모노드값이 자식노드의 값보다 작은 형태로 만들어진 완전이진트리, 루트노드에 항상 가장 작은 값 존재

 

 

 

 

 

 

---

 

 

 

 

2. 우선순위 큐 코드

---

 

□ 기본적인 메서드 종류

메서드	설명
add()	우선순위 큐에 원소를 추가, 큐가 꽉 찬 경우 에러 발생
offer()	우선순위 큐에 원소를 추가, 값 추가 실패 시 false 반환
poll()	우선순위 큐에서 첫 번째 값을 반환 및 제거, 비어있으면 null 반환
remove()	우선순위 큐에서 첫 번째 값을 반환 및 제거, 비어있으면 에러 발생
isEmpty()	우선순위 큐가 비어있는지 확인, 비어있다면 true, 비어있지않으면 false 반환
clear()	우선순위 큐를 초기화
size()	우선순위 큐의 원소의 수를 반환

 

 

(1) 우선순위 큐 (Priority Queue) 선언

• Priority Queue 를 사용하기 위해서 java.util.PriorityQueue 를 import 해야 한다.

import java.util.PriorityQueue;
import java.util.Collections;


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


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

 

 

 

 

 

---

 

 

 

(2) 우선순위 큐 (Priority Queue) 값 추가하기

• 데이터를 삽입할 때는 우선순위를 기준으로 최대힙 또는 최소힙을 구성한다. default 는 최소힙이다. 
• 최대 값이 우선순위인 큐 = 최대 힙, 최소 값이 우선순위인 큐 = 최소 힙 

import java.util.PriorityQueue;
import java.util.Collections;


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

Lower.add(1);
Lower.add(2);
Lower.add(3);

 

 

---

데이터가 삽입되는 과정 (최소힙일 때)

• 삽입된 데이터를 제일 마짐막 부분에 넣는다

 

 

 

 

 

 

• 부모와 비교하여 부모보다 작으면 swap

 

 

 

 

 

• 루트노드가 더 작기 때문에 더이상 swap 하지 않는다.

 

 

 

---

 

 

 

 

(3) 우선순위 큐 (Priority Queue) 값 삭제하기

• 우선순위가 가장 높은 값부터 제거된다. 

queue.poll();     // 우선순위가 가장 높은 값을 반환 및 제거 , 비어있다면 null 반환
queue.remove();   // 우선순위가 가장 높은 값을 반환 및 제거
queue.clear();    // 우선순위 큐에 있는 모든 요소 제거

 

 

---

데이터가 삭제되는 과정 (최소힙일 때)

• 루트 노드를 얻어낸 뒤 루트 노드를 다른 곳으로 빼두고 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행된다.

 

• 루트 노드를 뺴놓고 루트와 마지막 노드를 swap

 

 

• 사이즈를 줄이고 자식 노드 2개를 비교

 

 

• 최소힙이기 때문에 더 작은 5와 루트노드와 비교하여 작다면 swap

 

• 계속 비교하며 최소힙이 완성될때까지 반복한다.

 

 

---

 

 

(3) 우선순위 큐 (Priority Queue) 에서 우선순위가 가장 높은 값 출력

• peek() 메서드 사용

queue.peek();