[JAVA] 우선순위 큐 PriorityQueue

 

자바에서 우선순위 큐(Priority Queue)는 각 요소가 우선순위에 따라 정렬되며, 우선순위가 가장 높은 요소부터 접근할 수 있는 특별한 형태의 큐를 말한다. 이 구조는 특정 요소의 처리 순서를 우선순위에 따라 결정해야 할 때 유용하게 사용된다.

우선순위 큐의 특징

• 자동 정렬 기능: 우선순위 큐에 요소를 추가하면, 자동으로 우선순위에 따라 내부적으로 정렬된다. 이 정렬 과정은 힙(Heap)이라는 데이터 구조를 사용하여 효율적으로 이루어진다.
• 우선순위 결정 방식: 우선순위는 요소의 자연적인 순서(예를 들어, 숫자의 경우 낮은 수에서 높은 수로의 순서) 또는 개발자가 제공하는 Comparator를 통해 결정될 수 있다.
• 효율적인 요소 추가 및 제거: 요소를 큐에 추가하거나 우선순위가 가장 높은 요소를 큐에서 제거하는 데 필요한 시간은 대략 O(log n)으로, 매우 효율적이다.

우선순위 큐의 활용

우선순위 큐는 다양한 분야에서 널리 활용된다. 몇 가지 대표적인 예는 다음과 같다:

• 작업 스케줄링: 다양한 우선순위를 가진 작업들을 관리하고, 우선순위가 높은 작업부터 처리해야 할 때 우선순위 큐를 활용한다.
• 경로 찾기 알고리즘: 예를 들어, Dijkstra 알고리즘 같은 경로 찾기 알고리즘에서는 최소 비용의 경로를 우선적으로 탐색해야 할 때 우선순위 큐를 사용한다.
• 데이터 스트림의 중앙값 찾기: 동적인 데이터 스트림에서 중앙값을 효율적으로 찾아내는 데 우선순위 큐가 활용될 수 있다.

 

 

우선순위 큐 사용방법

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

PriorityQueue<Integer> pq = PriorityQueue<Integer>(Collections.reverseOrder());

pq.add(1);

pq.poll();

pq.peek();

pq.remove();

 

예제 문제

 

프로그래머스 - 더 맵게