우선순위 큐(PriorityQueue)

1. 우선순위 큐(Priority Queue)란?

---

일반적으로 Queue는 '선입선출(First-In, First-Out)의 대기열 규칙을 가지고 있다.

하지만 Java에서 제공하는 'Priority Queue'는 우선순위를 결정하여 들어온 순서와 상관없이 순위가 높은 엘리먼트가 나가게 된다. 

 

2. 예제

---

class Bag {
	int idx;
    int weight;
    
    public Bag(int idx, int weight) {
    	this.idx = idx;
        this.weight = weight;
    }
}

Bag 클래스를 PriorityQueue에 넣고, 가방의 무게에 따라 큐에서 나오게 하려고 한다.

 

"가방이 가벼운 것"부터 나오게 한다고 하자. 그러기 위해서는 Bag 클래스에 Comparable 인터페이스를 구현해야 한다.

 

class Bag implements Comparable<Bag> {
	int idx;
    int weight;
    
    public Bag(int idx, int weight) {
    	this.idx = idx;
        this.weight = weight; 
    }
    
    @Override
    public int compareTo(Bag bag) {
    	if(this.weight > bag.weight) {
        	return 1;
        } else if(this.weight < bag.weight) {
        	return -1;
        }
        return 0;
    }
}

가방이 가벼운 Bag 객체부터 꺼내기 위하여 compareTo 메소드를 오름차순으로 정렬되도록 구현하였다.

 

▶ PriorityQueue 사용

 

public static void main(String[] args) {
		Bag bag1 = new Bag(1, 5);
		Bag bag2 = new Bag(2, 9);
		Bag bag3 = new Bag(3, 14);
		Bag bag4 = new Bag(4, 10);
		Bag bag5 = new Bag(5, 1);

		java.util.PriorityQueue<Bag> priorityQueue = new java.util.PriorityQueue<>();

		priorityQueue.offer(bag1);
		priorityQueue.offer(bag2);
		priorityQueue.offer(bag3);
		priorityQueue.offer(bag4);
		priorityQueue.offer(bag5);

		while(!priorityQueue.isEmpty()) {
			Bag bag = priorityQueue.poll();
			System.out.printf("bag's idx = %d \n", bag.idx);
		}

	}

결과 >

bag's idx = 5 
bag's idx = 1 
bag's idx = 2 
bag's idx = 4 
bag's idx = 3 

무게가 작은 가방의 idx부터 출력한다. 

 

▶ Reversed Order

 

우선순위를 오름차순에서 내림차순으로, 또는 내림차순에서 오름차순으로 바꾸고 싶을 때 사용한다.

 

PriorityQueue<Bag> reversedPriorityQueue = PriorityQueue<>(Collections.reverseOrder());
reversedPriorityQueue.addAll(priorityQueue);
System.out.println("-------------reversedOrder-------------");
while(!reversdPriorityQueue.isEmpty()) {
	Bag bag = reversedPriorityQueue.poll(); 
    System.out.printf("bag's idx = %d \n", bag.idx);
}

-------------reversedOrder-------------
bag's idx = 3 
bag's idx = 4 
bag's idx = 2 
bag's idx = 1 
bag's idx = 5