Java 에서 PriorityQueue(우선 순위 큐) 는 Heap 의 기능을 가진 Queue 이다. 기본적인 Queue 와 달리 Queue 에 값을 넣은 순서대로 처리되는 것이 아니라, 지정된 우선순위에 따라서 처리가 되는데, PriorityQue 에서는 기본으로 natural ordering(숫자의 오름 차순, 문자의 알파벳순 정렬 등) 을 기반으로 우선 순위가 지정된다.
예를 들어, 일반적인 Queue 에 아래의 순서대로 숫자 값을 넣고,
5 -> 3 -> 1 -> 2 -> 4
Queue 에서 값을 순서대로 꺼내면
5 -> 3 -> 2 -> 1 -> 4
이렇게 된다.
하지만, PriorityQueue 에 동일하게 값을 넣고 꺼내면,
1 -> 2 -> 3 -> 4 -> 5
와 같이 값이 정렬되어 나온다. 이것을 Min Heap 이라고 하는데 Queue 제일 처음(head)에 가장 장 작은 값이 위치한다. 아무런 정렬 방식을 정하지 않으면, 숫자의 경우에는 값을 넣을 때마다 오름 차순으로 PriorityQueue 내에서 정렬이 일어난다.
PriorityQueue 의 생성자 중에는 Comparator 인터페이스를 파라미터를 받는 것이 있는데, Comaprator 구현을 사용해서 정렬 방식을 바꿀 수 있다.
PriorptyQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
위의 코드는 숫자의 내림 차순으로 정렬한다. 즉 Max Heap 을 사용한다.
@Test
public void test() {
// max heap
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.add(1);
pq.add(3);
pq.add(2);
pq.add(4);
assertEquals(4, (int)pq.poll());
assertEquals(3, (int)pq.poll());
assertEquals(2, (int)pq.poll());
assertEquals(1, (int)pq.poll());
}
PriorityQueue를 활용한 알고리즘 문제
중앙값 (median) 찾기
주어진 일련의 숫자 배열에서 중앙값을 찾는 문제
입력) 10, 43, 56, 37, 19, 66, 74, 23, 41, 24
출력) (37 + 41) / 2 -> 39
힌트
Max Heap 과 Min Heap 을 각각 사용해서, 입력 값의 작은 쪽 절반은 Max Heap 에 넣고, 큰 쪽 절반은 Min Heap 에 넣는다. 그러면 Max Heap 의 제일 앞에는 작은 쪽 절반 값에서 가장 큰 값이 저장되고, Min Heap 의 제일 앞에서는 큰 쪽 절반 값 중에서 가장 작은 작은 값이 저장된다.
Max Heap:
37 -> 24 -> 23 -> 19 -> 10
Min Heap:
41 -> 43 -> 56 -> 66 -> 74
Answer
public class MedianFinder {
private PriorityQueue<Integer> maxHeap;
private PriorityQueue<Integer> minHeap;
public MedianFinder() {
maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap = new PriorityQueue<>();
}
public void addNumber(int num) {
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
if(maxHeap.size() < minHeap.size()) {
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
if(maxHeap.size() == minHeap.size()) {
return (double)((maxHeap.peek() + minHeap.peek()) / 2);
}
return maxHeap.peek();
}
}
@Test
public void test() {
// max heap
PriorityQueue<Integer> pq = new PriorityQueue<>(10, (Integer a, Integer b) -> a <= b ? 1 : -1);
pq.add(1);
pq.add(3);
pq.add(2);
pq.add(4);
assertEquals(4, (int)pq.poll());
assertEquals(3, (int)pq.poll());
assertEquals(2, (int)pq.poll());
assertEquals(1, (int)pq.poll());
}
Find Median From Data Stream 참고
Jinwoo's Blog 