[JAVA] 우선순위큐 (Priority Queue)

PriorityQueue

PriorityQueue란 데이터가 들어오는데로 나가는 것(FIFO)이 아니라 우선순위를 결정하고 우선순위가 높은 데이터가 먼저 나가는 구조를 가진다.

 

PriorityQueue 특징

1. 우선순위가 높은 데이터가 먼저 나가는 방식.

  PriorityQueue에 들어가는 객체는 비교가 가능한 기준이 있어야한다.

  (사용자가 생성한 객체를 사용하고 싶다면 해당 객체에 compareTo 메소드를 정의하여 우선순위 룰을 정의하면된다.)

2. 이진트리 구조로 되어있다.

3. 우선순위가 중요시 되는 상황에 사용된다.

 

PriorityQueue 사용

//낮은 숫자가 우선 순위
PriorityQueue<Integer> pqLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위
PriorityQueue<Integer> pqHighest = new PriorityQueue<>(Collections.reverseOrder());

 

 

 

PriorityQueue 동장방식

Add

pqLowest.add(1);
pqLowest.add(10);
pqLowest.add(8);
pqLowest.add(17);
pqLowest.add(25);
pqLowest.add(16);
pqLowest.add(7);

출처 : https://coding-factory.tistory.com/603

 

Poll

출처 : https://coding-factory.tistory.com/603

 

 

 

PriorityQueue Class사용하여 우선순위 부여

compareTo메소드 구현

class DevLog implements Comparable<DevLog> {

    private int weight;
    private String title;

    public DevLog(int weight, String title) {
        this.weight = weight;
        this.title = title;
    }
    public int getWeight() {
        return this.weight;
    }

    public String getTitle() {
        return this.title;
    }

    @Override
    public int compareTo(DevLog devLog) {

        if (this.weight > devLog.weight)
            return 1;
        else if (this.weight < devLog.weight)
            return -1;
        return 0;
    }
}

 

 public static void main(String[] args) {

        PriorityQueue<DevLog> priorityQueue = new PriorityQueue<>();

        priorityQueue.add(new DevLog(10, "DevLog1"));
        priorityQueue.add(new DevLog(1, "DevLog2"));
        priorityQueue.add(new DevLog(3, "DevLog3"));
        priorityQueue.add(new DevLog(333, "DevLog4"));
        priorityQueue.add(new DevLog(25, "DevLog5"));
        priorityQueue.add(new DevLog(999, "DevLog6"));

        while (!priorityQueue.isEmpty()) {
            DevLog devLog = priorityQueue.poll();
            System.out.println("weight : " + devLog.getWeight() + " title : " + devLog.getTitle());
        }
 }

 

관련 문제

[알고리즘/문제] - 백준 1715 [카드 정렬하기] - JAVA

[알고리즘/문제] - 백준 1202 [보석 도둑] - JAVA