[자료구조] PriorityQueue

우선순위 큐 (Priority Queue)

 

• dequeue할 때, 우선순위가 높은 데이터가 먼저 나옴
• 우선순위가 같은 경우는 Queue와 동일하게 FIFO!!
• enqueue, dequeue는 최소/대 힙 삽입, 삭제와 같다

 

 

1. 우선순위 낮은 숫자 순

 

PriorityQueue<Integer> pq = new PriorityQueue();
pq.add(5);
pq.add(7);
pq.add(3);
pq.add(1);
pq.add(9);
System.out.println(Arrays.toString(pq.toArray()));

// [1, 3, 5, 7, 9]

 

 

2. 우선 순위 높은 숫자 순

 

PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());
pq2.add(5);
pq2.add(7);
pq2.add(3);
pq2.add(1);
pq2.add(9);
System.out.println(Arrays.toString(pq2.toArray()));

// [9, 7, 3, 1, 5]

 

 

3. Comparable 인터페이스 구현

 

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

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int compareTo(Person o) {
        // 1: 변경 안함
        // -1: 변경
        // 새롭게 추가하는 데이터가 더 작을 때 변경 (작은 값이 위로 올라감, 오름 차순)
        return this.age >= o.age ? 1 : -1;

        // 새롭게 추가하는 데이터가 더 클 때 변경 (큰 값이 위로 올라감, 내림 차순)
//        return this.age >= o.age ? -1 : 1;
    }
}

PriorityQueue<Person> pq = new PriorityQueue<>();

 

 

4. 람다식 이용 

 

• 3번과 같이 Comparable 인터페이스를 구현하지 않았을 때

PriorityQueue<Person> pq2 = new PriorityQueue<>(
                (Person p1, Person p2) -> p1.age >= p2.age ? 1 : -1);