PriorityQueue를 이용한 최소 힙 구현 (JAVA)

우선순위 큐 PriorityQueue

선입선출인 Queue와 달리 우선 순위를 설정하여 우선 순위가 높은 순서대로 데이터를 꺼내는 구조 (우선 순위가 같으면 선입 선출)

힙(Heap)

완전 이진트리 형태로 최대, 최솟값 빠르게 찾아내는데 유용한 자료구조

• 장점 : 빠른 삽입과 삭제 (O(log n))
• 단점 : 특정 요소 찾기 어려움(O(n)), 정렬 유지 오버헤드 (삽입. 삭제 연산 시에 정렬 조정해야함)

최소힙

루트 노드가 최솟값이 되고, 부모 노드의 key는 자식 노드의 key보다 작아야 한다.

Copy

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

minHeap.add(1);
minHeap.add(10);
minHeap.add(9);
minHeap.add(2);

 

 

최소 힙의 특성: 부모 노드 ≤ 자식 노드 완전 이진 트리 : 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있으며, 왼쪽→오른쪽 순서로 채워지는 이진 트리

자식 간의 크기 순서는 우선순위 큐에서 보장하지 않으며 완전 이진 트리를 만족하는 한 순서가 어떻게 배치될 지 모른다.

실전 문제 (backjoon 1927)

코드 전문 

package backjoon;
import java.util.*;
import java.io.*;

class Main{
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		PriorityQueue<Integer> minHeap = new PriorityQueue<>();
		
		int n = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < n ; i++) {
			int num = Integer.parseInt(br.readLine());
			if(num>0) {
				minHeap.add(num);
			}
			else{//0
				
				if(!minHeap.isEmpty()) {
					sb.append(minHeap.peek()).append("\n");
					minHeap.poll();
				}
				else {
					sb.append(0).append("\n");
				}
				
			}
		}
		
		System.out.println(sb);
	}
}

최소 힙에서 최솟값 삭제를 위한 메서드

poll() : 최솟값을 반환하고 힙에서 제거

remove() : 최솟값을 제거(특정 값 지정이 없을 때는 poll과 동일한 동작을 한다)