[자바] 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

 

개념

일반적인 큐에서는 먼저 들어간 데이터가 먼저 나오는 FIFO 구조였으나, 우선순위 큐에서는 그렇지 않다.

관리하는  데이터마다  우선순위가 있으며 Dequeue시 우선순위가 높은 순서대로 나간다.

단, 우선순위가 같다면 FIFO 방식으로 나간다.

자바에서는 기본적으로 PriorityQueue를 제공하고있다.

 

구현방법

일반적인 상황에서 enqueue와 dequeue의 횟수가 비슷하게 발생한다.

그렇기때문에 전체적인 복잡도가 낮은 힙을 이용해 주로 구현한다.

 

우선순위 큐를 힙으로 구현한다면, 삽입 및 삭제 후 우선순위에 따라 데이터가 재배치되는 원리는 최소힙 및 최대힙의 삽입 & 삭제와 동일하다.

https://imcoding.tistory.com/7

힙(Heap) - 최대힙 / 최소힙 개념과 구현. java

 

 

 

사용예시

자바에서 제공하는 PriorityQueue 클래스를 사용해보겠다.

        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()));
        
        // 아래처럼도 가능하다.
        
        PriorityQueue<Integer> pq2 = new PriorityQueue<>((x, y) -> x - y);

        pq2.add(5);
        pq2.add(7);
        pq2.add(3);
        pq2.add(1);
        pq2.add(9);
        System.out.println(Arrays.toString(pq2.toArray()));

출력: 1, 3, 5, 7, 9

단순 오름차순이 아닌 것에 주의하자. 힙에서 삽입되는 메커니즘에 따라 정렬된 모습이다.

 

내림차순으로도 정렬해보겠다.

        PriorityQueue pq2 = new PriorityQueue<>(Collections.reverseOrder());
        pq2.add(5);
        pq2.add(1);
        pq2.add(4);
        pq2.add(3);
        pq2.add(2);
        System.out.println(Arrays.toString(pq2.toArray()));
        
        // 아래처럼도 가능하다.
        
        PriorityQueue<Integer> pq2 = new PriorityQueue<>((x, y) -> y - x);

        pq2.add(5);
        pq2.add(1);
        pq2.add(4);
        pq2.add(3);
        pq2.add(2);
        System.out.println(Arrays.toString(pq2.toArray()));

출력: 5, 3, 4, 1, 2

Collections.reverseOrder를 사용하면 최대힙에서와 같은 원리로 동작한다.

부모노드의 값과 비교해서 더 큰값을 위로 올려준다고 보면 된다. (형제노드간의 크기차이는 고려하지 않는다)

 

 

연습문제

간단한 연습문제를 풀어보겠다.

name배열과 age배열을 받아서 age순으로 오름차순 또는 내림차순 정렬하면 된다.

import java.util.PriorityQueue;

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

    @Override
    public int compareTo(Person o) {
    
// 새롭게 추가하는 데이터(this.age) 값을 비교하며 더 작다면 오름차순이 되게끔 정렬한다.
        return this.age >= o.age ? 1 : -1;
        
// 내림차순  return this.age >= o.age ? -1 : 1;
    }

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

public class Practice1 {
    public static void solution(String[] name, int[] age) { // 우선순위큐 생성 및 출력 메서드 생성
        PriorityQueue<Person> queue1 = new PriorityQueue<>();
        for (int i = 0; i < name.length; i++) {
            queue1.offer(new Person(name[i], age[i]));
        } // 데이터가 name, age 두개씩 들어있으므로, Comparable 인터페이스를 이용해 정렬한다.

        while (!queue1.isEmpty()) {
            Person p = queue1.poll();
            System.out.println(p.name + " " + p.age);
        }
    }
    
    public static void main(String[] args) {
        String[] name = {"A", "B", "C", "D", "E"};
        int[] age = {30, 20, 45, 62, 35};

        solution(name, age);

        PriorityQueue<Person> queue2 = new PriorityQueue<>();
    }
}

 

출력
B 20
A 30
E 35
C 45
D 62

 

 

위에서 풀어본 문제와 동일한 문제를 Comparable 인터페이스 구현 없이 람다식으로 풀어보겠다.

import java.util.PriorityQueue;

class Person {

    String name;
    int age;

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

public class Practice1 {
    public static void main(String[] args) {
        String[] name = {"A", "B", "C", "D", "E"};
        int[] age = {30, 20, 45, 62, 35};  

        PriorityQueue<Person> queue2 = new PriorityQueue<>(
                (Person p1, Person p2) -> p1.age >= p2.age ? 1 : -1); // 람다식을 통해 객체생성

        for (int i = 0; i < name.length; i++) {
            queue2.offer(new Person(name[i], age[i]));
        }

        while (!queue2.isEmpty()) {
            Person p = queue2.poll();
            System.out.println(p.name + " " + p.age);
        }
    }
}