[알고리즘] 우선순위 큐, 힙

우선순위 큐는 들어오는 순서에 상관없이 우선순위가 높은 데이터가 먼저 나가는 구조이다.

우선순위 큐는 힙을 이용해서 구현한다.

PriorityQueue를 이용해서 우선순위 큐를 구현하며, 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야 한다. Comparable Interface를 구현하면 compareTo 메서드를 오버라이드 하게 되고, 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue가 알아서 우선순위가 높은 객체를 추출해준다.

 

PriorityQueue 선언 방법

// 우선순위가 낮은 숫자가 먼저 나옴
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

// 우선순위가 높은 숫자가 먼저 나옴
PriorityQueue<Integer> priorityQueue = PriorityQueue<>(Collections.reverseOrder());

 

 

관련 문제

https://www.acmicpc.net/problem/11286