우선순위큐(PriorityQueue)

1. PriorityQueue 란?

일반적인 큐는 먼저 들어간 데이터가 먼저 나가는 구조인 FIFO 형식의 자료구조입니다.

반면에 우선순위 큐의 경우 들어가는 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다.

우선순위 큐의 경우 힙 자료구조를 통해서 구현될 수 있습니다. ( 또한 다른 자료구조를 통해서 구현될 수 있음 )

2. PriorityQueue 선언 방법

// 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>();

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

3. 기본적인 메소드

add() :  　    우선순위 큐에 원소를 추가. 큐가 꽉 찬 경우 에러 발생
offer()  :       우선순위 큐에 원소를 추가. 값 추가 실패 시 false를 반환
poll() :         우선순위 큐에서 첫 번째 값을 반환하고  제거, 비어있으면 null 반환
remove() :   우선순위 큐에서 첫 번째 값을 반환하고  제거, 비어있으면 에러 발생
isEmpty() :   우선순위 큐에서 첫 번째 값을 반환하고  제거, 비어있으면 에러 발생
clear() :       우선순위 큐를 초기화
size() :         우선순위 큐에 포함되어 있는 원소의 수를 반환

4. PriorityQueue 자바 사용방법

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {

        // 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
        PriorityQueue<Integer> pQ = new PriorityQueue<>();

        pQ.offer(1);    // pQ에 원소 1 추가
        pQ.offer(6);    // pQ에 원소 6 추가
        pQ.offer(2);    // pQ에 원소 2 추가

        // pQ가 비어있면: true, 그렇지 않으면 : false
        while(!pQ.isEmpty()) {
            // pQ에 첫 번째 값을 반환하고 제거, 비어있다면 null 반환
            System.out.println("pQ.poll() = " + pQ.poll());
        }

    }
}

우선순위큐를 이용한 최소힙/최대힙

import java.io.IOException;
import java.util.Collections;
import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) throws IOException {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        System.out.println("최소 힙");
        runHeapTest(minHeap);

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        System.out.println("최대 힙");
        runHeapTest(maxHeap);
    }

    private static void runHeapTest(PriorityQueue<Integer> heap) {
        heap.add(1);
        heap.add(8);
        heap.add(5);
        heap.add(2);
        heap.add(3);

        while (!heap.isEmpty()) {
            System.out.println(heap.poll());
        }
    }
}

해당 결과는 다음과 같습니다. 

최소힙은 작은 수 부터 순서대로 출력, 최대힙은 큰 수부터 순서대로 출력됩니다.

최소 힙
1
2
3
5
8
최대 힙
8
5
3
2
1