7. 우선순위 큐(Priority Queue) & 힙(Heap)

1. 우선 순위 큐 개념 파악

• 일반 큐 : FIFO (먼저 들어온 순서대로 먼저 나간다.)
• 우선순위 큐 : 늦게왔어도 우선 순위가 높다면 먼저 나간다.

즉, 들어간 순서와 상관없이 우선순위가 높은 데이터가 가장 먼저 나온다.

 

2. 힙(Heap)이란?

우선순위 큐를 구현하는데에 있어서 가장 효율적인 자료구조가 바로 힙이다. 생긴 건 트리(Tree)처럼 생겼는데, 반만 정렬된 상태이다.

• 모양: 트리(Tree)구조. (부모-자식 관계가 있는 구조)
• 특징
  • 최소 힙(Min Heap): 제일 작은 숫자가 항상 맨 꼭대기(Root)에 온다. (자바 기본값)
  • 최대 힙(Max Heap): 제일 큰 숫자가 항상 맨 꼭대기(Root)에 온다.
• 핵심 원리: 데이터가 들어오거나 나갈 때, 자동으로 대 소를 비교해서 최소값 또는 최대값을 맨 위로 올려 보낸다.

 

3. 구현 클래스

import java.util.PriorityQueue;

// 1. 낮은 숫자가 우선 (기본값, 최소 힙)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 2. 높은 숫자가 우선 (반대, 최대 힙) -> 코딩테스트에 자주 나옴!
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

 

최대 힙을 구현하기 위해서는 Collections.reverseOrder()를 이용하여 반대로 뒤집는다.

 

3.1. 구현 예시 (기본 정렬 우선순위 큐)

PriorityQueue<String> pq = new PriorityQueue<>();

pq.offer("Banana");
pq.offer("Apple");
pq.offer("Cherry");

// 넣은 순서는 뒤죽박죽이지만...
System.out.println(pq.poll()); // 결과: Apple (A가 제일 작음)
System.out.println(pq.poll()); // 결과: Banana (B)
System.out.println(pq.poll()); // 결과: Cherry (C)

 

3.2. 구현 예시 (커스텀 우선순위 큐)

// 문자열의 길이 기준으로 비교하여 우선순위를 나눈다.
PriorityQueue<String> pq = new PriorityQueue<>((s1, s2) -> s1.length() - s2.length());

pq.offer("Banana"); // 길이 6
pq.offer("Kiwi"); // 길이 4
pq.offer("Apple"); // 길이 5

System.out.println(pq.poll()); // 결과: Kiwi (길이가 제일 짧아서 가장 먼저 나온다.)
System.out.println(pq.poll()); // 결과: Apple
System.out.println(pq.poll()); // 결과: Banana

4. 구현 메서드

구분	메서드	설명	시간 복잡도
추가	offer(E e) 또는 add	큐에 데이터를 넣는다. 내부적으로 즉시 우선순위를 비교하여 자리를 잡는다.	O(log N)
삭제	poll()	가장 우선순위가 높은 (맨 앞) 데이터를 꺼내고 지운다. 빠진 자리를 채우기 위해 다시 정렬한다.	O(log N)
확인	peek()	가장  우선순위가 높은 데이터를 확인한다. 꺼내지 않으므로 큐의 상태는 변하지 않는다.	O(1)
탐색	contains(Object o)	특정 데이터가 큐 안에 있는지 처음부터 끝까지 찾는다. 힙은 정렬 상태가 아니므로 싹 탐색해야 한다.	O(N)
제거	remove(Object o)	맨 앞(Root)이 아닌, 특정 값을 찾아서 지운다. 찾는 과정에서 시간이 지연된다.	O(N)
크기	size()	현재 큐에 들어있는 데이터 개수를 반환한다.	O(1)

 

 

5. 일반 큐와의 차이점

일반 큐(Queue)

• 모양 : 긴 파이프 관
• 동작 : 뒤로 들어가서 앞으로 나온다.
• 내부 : 그냥 줄 서 있는 순서 그대로 저장한다.

 

우선순위 큐(Priority Queue)

• 모양 : 피라미드(트리) 모양. (Heap)
• 동작 : 들어갈 땐 맘대로지만, 나갈 땐 우선 순위가 가장 높은 값이 나간다.
• 내부 : 겉으로는 리스트처럼 보이지만, 실제로는 부모-자식 관계로 엮여서 누가 더 우선 순위가 높은지 비교한다.