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

1. 우선순위 큐란?

우선순위 큐는 선입선출의 입출력을 따르는 일반적인 큐와 다르게

입력된 순서와 상관없이 우선순위가 가장 높은 데이터를 가장 먼저 출력한다.

 

우선순위 큐는 힙을 이용하여 구현된 자료구조이다.

데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소힙을 구성하고 데이터를 꺼낼 때 루트 노드를 꺼낸다.

루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮긴다.

 

2. 예제

1) Integer형 우선순위 큐

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

priorityQueue.add(4); //offer(); 메소드를 사용해도 동일하게 추가됩니다.
priorityQueue.add(3);
priorityQueue.add(2);
priorityQueue.add(1);

Integer poll = priorityQueue.
System.out.println(poll); //출력결과 1

일반적으로는 가장 작은 값이 우선이 된다.

다른 오름차순으로 사용하고 싶다면 Compartor 클래스나 Comparable 인터페이스를 이용해야 한다.

정렬기준으로 정하는 것과 동일하고 Integer와 같은 숫자는 Collections.reversOrder()를 사용하면

간편하게 우선순위를 변경할 수 있습니다.

 

우선순위를 바꿔준 예제이다.

//우선순위를 높은 숫자위주로 변경
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

priorityQueue.add(1); //offer(); 메소드를 사용해도 동일하게 추가됩니다.
priorityQueue.add(2);
priorityQueue.add(3);
priorityQueue.add(4);

Integer poll = priorityQueue.
System.out.println(poll); //출력결과 4

2) 객체를 활용한 우선순위 큐

name과 age 속성을 가진 Student클래스를 만들고

Student객체의 나이를 기준으로 나이가 많은 순으로 우선순위 큐를 구성한다.

 

우선순위가 한 가지의 속성으로만 결정될 필요는 없다.

새로운 속성 값을 추가하고 Comparable, Comparator 를 잘 구현해주면

여러가지의 조건으로 우선 순위를 결정할 수 있다.

Student 클래스

class Student implements Comparable<Student> {
    String name;
    int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Student target) {
        return this.age <= target.age ? 1 : - 1;
    }

    @Override
    public String toString() {
        return "이름 : " + name + ", 나이 : " + age;
    }
}

Student 클래스에 Comparable의 compareTo() 를 오버라이딩 하여 구현한다.

age 값을 기준으로 반환 값이 음수, 양수 인지에 따라 우선순위가 결정된다.

아래의 예제는 나이가 많은 순을 구현한 것이다. (나이가 많은 학생이 우선순위가 높다.)

 

우선순위 큐 생성 및 실행

public static void main(String[] args) {
    PriorityQueue<Student> priorityQueue = new PriorityQueue<>();
	
    // 값 추가
    priorityQueue.offer(new Student("김철수", 20));
    priorityQueue.offer(new Student("김영희", 100));
    priorityQueue.offer(new Student("한택희", 66));
    priorityQueue.offer(new Student("이나영", 7));
    priorityQueue.offer(new Student("이혁", 43));
    priorityQueue.offer(new Student("안영희", 100));
    
    // 나이가 많은 순으로 학생들 목록을 출력
    while (!priorityQueue.isEmpty())
        System.out.println(priorityQueue.poll());
}

나이가 많은 순.
이름 : 김영희, 나이 : 100
이름 : 안영희, 나이 : 100
이름 : 한택희, 나이 : 66
이름 : 이혁, 나이 : 43
이름 : 김철수, 나이 : 20
이름 : 이나영, 나이 : 7

 

참고: Java 우선순위 큐(Priority Queue) 와 Comparable, Comparator