Java 코딩 테스트 준비 - PriorityQueue와 힙 구현

PriorityQueue

개요

• 우선순위 큐는 먼저 들어간 데이터가 먼저 나오는 일반적인 큐와는 다르게 데이터를 꺼낼 때 우선순위가 가장 높은 데이터가 가장 먼저 나온다.
• 우선순위 큐는 힙을 이용하여 구현하는 것이 일반적이다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸다.

기본 사용법

그냥 사용하면 기본은 최소힙이다. 값을 추가하는 방법은 add 또는 offer이 있다. 값을 제거하는 방법은 poll, remove가 있다. clear는 초기화.

public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
 
        priorityQueue.add(4);
        priorityQueue.add(6);
        priorityQueue.add(5);
        priorityQueue.add(1);
		//priorityQueue.offer(3);   // priorityQueue 값 3 추가
 
        
        while(!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
			//priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거, 비어있다면 null
			//priorityQueue.remove();     // priorityQueue에 첫번째 값 제거
			//priorityQueue.clear();      // priorityQueue에 초기화  
        }
}

// 결과 : 1 4 5 6

peek() 도 알아두자. peek()은 가장 위에 있는 첫번째 값을 확인만 하는 메서드이다. 파이썬으로 따지면 priorityQueue[0] 을 확인하는 거겠네. 근데 자바에서는 그렇게 사용할 수 없으니...

정렬 기준 정하기

만약 최대힙으로 사용하고 싶다면? PriorityQueue에 Comparator를 구현해주면 된다.

public PriorityQueue(java.util.Comparator<? super E> comparator )

가장 간단한 방법으로는 Collections.reverseOrder()를 사용할 수도 있고. 직접 Comparator를 구현할 수도 있고, 람다를 사용할 수도 있다. 정렬하는 방법 포스팅에서 참고바람.

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(
														Collections.reverseOrder());

참고. PriorityQueue를 사용하는 코딩테스트 문제 예시

• https://school.programmers.co.kr/learn/courses/30/lessons/155651