PriorityQueue

PriorityQueue (우선순위 큐)는 우선순위에 따라 정리되어 있으며,
우선순위가 가장 높은 요소에 먼저 접근할 수 있는 자료구조이다.

 

• PriorityQueue 의 구현을 위해서는 Heap 이 사용된다.
• PriorityQueue는 기본적으로 Min Heap을 사용한다.
• 가장 높은 우선순위를 갖는 요소는 root 노드에 위치하게 된다.
• 이에 따른 요소의 추가와 삭제 과정은 다음과 같다.
   
  • 추가 과정
    1. 새로운 요소를 Heap의 마지막 노드에 위치시킨다.
    2. 부모노드와 비교하며 적절한 위치에 배치한다.
  • 삭제 과정
    1. 우선순위가 제일 높은 요소를 뽑는다. (root 노드)
    2. 이후 Heap의 마지막 노드를 root 노드의 위치로 이동시킨다.
    3. 자식노드와 비교하며 적절한 위치에 배치한다.

 

PriorityQueue 클래스 메서드

• add / offer(E e) : 지정된 요소를 우선순위 큐에 추가한다.
• peek() : 우선순위 큐에서 가장 우선순위가 높은 요소를 반환한다. 큐에서 요소를 삭제하지 않는다.
• poll() : 우선순위 큐에서 가장 우선순위가 높은 요소를 반환하고, 해당 요소를 큐에서 제거한다.
• remove(Object o) : 지정된 요소를 우선순위 큐에서 제거한다.
• clear() : 우선순위 큐에서 모든 요소를 제거한다.
• size() : 우선순위 큐의 요소 수를 반환한다.
• toArray() : 우선순위 큐의 요소를 배열로 반환한다.
• iterator() : 우선순위 큐의 요소에 대한 반복자(iterator)를 반환한다.
• comparator() : 우선순위 큐에서 사용하는 Comparator 객체를 반환한다.

Comparator 인터페이스를 구현하면 원하는 우선순위 정책에 따라 우선순위 큐를 사용할 수 있다.

 

 

 

---

 

 

Comparator와 Comparable 인터페이스를 구현하면
원하는 우선순위 정책에 따라 우선순위 큐를 사용할 수 있다.

둘 다 객체 비교를 위한 인터페이스이다.

 

 

Comparator 클래스

comparator 클래스는 두 개의 객체를 비교하는데 사용되며, 우선순위 큐에서는 이를 이용하여 요소의 우선순위를 결정한다.

우선 간단하게 기본 오름차순 정렬에서 내림차순 정렬로 변경하는 코드는 다음과 같다.

import java.util.Comparator;
import java.util.PriorityQueue;

public class Example {
    public static void main(String[] args) {
        // 정수형 우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        
        // 요소 추가
        pq.add(3);
        pq.add(1);
        pq.add(2);
        
        // 요소 제거
        System.out.println(pq.poll());  // 3
        System.out.println(pq.poll());  // 2
        System.out.println(pq.poll());  // 1
    }
}

위와 같이 Comparator.reverseOrder() 메서드를 이용하면 정렬 순서를 간단하게 뒤집을 수 있다.

 

• Comparator의 경우 객체 외부에서 두 객체를 비교하는 기준의 역할을 한다.
• Comparable의 경우 객체 내부에 비교 기준을 부여한다.

compare() 메서드를 구현하여 두 개의 객체를 비교하고 요소의 우선순위를 결정하는 예시는 다음과 같다.

import java.util.*;

class Person {
    private String name;
    private int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    public String getName() {
        return name;
    }
    
    public int getAge() {
        return age;
    }
}

class PersonComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        // 나이를 기준으로 오름차순 정렬
        return Integer.compare(p1.getAge(), p2.getAge());
    }
}

public class Main {
    public static void main(String[] args) {
        // Person 객체를 우선순위 큐에 추가하며, 나이를 기준으로 오름차순 정렬
        PriorityQueue<Person> pq = new PriorityQueue<>(new PersonComparator());
        
        // Person 객체 추가
        pq.add(new Person("Alice", 25));
        pq.add(new Person("Bob", 30));
        pq.add(new Person("Charlie", 20));
        
        // Person 객체 제거
        System.out.println(pq.poll().getName());  // Charlie
        System.out.println(pq.poll().getName());  // Alice
        System.out.println(pq.poll().getName());  // Bob
    }
}

 

 

Comparable 인터페이스

Comparable 인터페이스의 compareTo 메서드를 오버라이딩 하여 우선순위를 결정하는 예시는 다음과 같다.

import java.util.*;

class Person implements Comparable<Person> {
    private String name;
    private int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    public String getName() {
        return name;
    }
    
    public int getAge() {
        return age;
    }
    
    @Override
    public int compareTo(Person p) {
        // 나이를 기준으로 오름차순 정렬
        return Integer.compare(age, p.age);
    }
}

public class Main {
    public static void main(String[] args) {
        // Person 객체를 우선순위 큐에 추가하며, 나이를 기준으로 오름차순 정렬
        PriorityQueue<Person> pq = new PriorityQueue<>();
        
        // Person 객체 추가
        pq.add(new Person("Alice", 25));
        pq.add(new Person("Bob", 30));
        pq.add(new Person("Charlie", 20));
        
        // Person 객체 제거
        System.out.println(pq.poll().getName());  // Charlie
        System.out.println(pq.poll().getName());  // Alice
        System.out.println(pq.poll().getName());  // Bob
    }
}

 

 

 

 

Comparable에 대한 다른 예시는 다음 문제가 있다.

좌표 정렬