우선순위 큐(Priority Queue)

우선순위 큐

우선순위 큐 개념

우선순위 큐(Priority Queue)는 큐나 스택과 비슷한 축약 자료형이다. 그러나 각 원소들은 우선순위를 갖고 있다. 우선순위 큐에서 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 만약 두 원소가 같은 우선순위를 가진다면 큐 방식으로 순서에 의해 처리된다.

우선순위 큐가 힙입라는 것은 널리 알려진 오류이다. 우선순위 큐는 리스트나 맵과 같이 추상적인 개념이다. 마치 리스트는 연결 리스트나 배열로 구현될 수 있는 것과 같이 우선순위 큐는 힙이나 다양한 다른 방법을 이용해 구현될 수 있다.

우선순위 큐는 큐와 유사하지만 우선순위가 높은 원소가 먼저 처리된다. 위에서 설명했듯이 우선순위 큐는 추상적인 개념이고, 우선순위 큐의 기능을 사용할 수 있도록 구현체로 Heap을 이용한다.
Priority Queue = ADT (추상자료형)
Heap = Data Structure (실제 구현체)

우선순위 큐 시간복잡도 활용

우선순위 큐는 구현체로 힙을 사용하고, 힙(Heap)은 최댓값이나 최솟값을 구하는데 빠르게 찾아내기 위해 고안된 완전 이진 트리(Complete Binary Tree)를 기반으로 한 자료구조이다. 따라서 우선순위 큐의 시간복잡도는 O(log N)이다.

우선순위 큐의 활용은 여러가지가 있겠지만 대표적으로 2가지만 소개하겠다.

1. 응급실과 같이 우선순위를 중요시해야 하는 상황
2. CPU의 프로세스들을 효율적으로 사용하기 위한 프로세스 스케줄링(process scheduling)

Priority Queue를 이용하여 기본형 우선순위 사용법

• offer(): 우선순위 큐에서 원소 1개 추가, 큐가 꽉 찬 경우 false 반환
• add(): 우선순위 큐에서 원소 1개 추가, 큐가 꽉 찬 경우 에러 발생
• poll(): 우선순위 큐에서 원소 1개 제거, 비어있으면 null 반환
• remove(): 우선순위 큐에서 원소 1개 제거, 비어있으면 NoSuchElementException 반환
• isEmpty(): 우선순위 큐가 비어있는지 반환
• clear(): 우선순위 큐에 있는 모든 원소 제거
• size(): 우선순위 큐 사이즈 반환

public class Ex01 {
    public static void main(String[] args) {
        // int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        pQ.offer(1);
        pQ.offer(9);
        pQ.offer(4);
        pQ.offer(2);
        pQ.offer(5);

        Integer a = pQ.poll();
        System.out.println("a = " + a); // 1

        Integer b = pQ.poll();
        System.out.println("b = " + b); // 2

        Integer c = pQ.poll();
        System.out.println("c = " + c); // 4
    }
}

• PriorityQueue<Integer> pQ = new PriorityQueue<>(); : PriorityQueue를 기본형(primitive type)으로 선언할 경우 가장 낮은 숫자가 가장 먼저 꺼낼 수 있다.

public class Ex01 {
    public static void main(String[] args) {
        // int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
        PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
        pQ.offer(1);
        pQ.offer(9);
        pQ.offer(4);
        pQ.offer(2);
        pQ.offer(5);

        Integer a = pQ.poll();
        System.out.println("a = " + a); // 9

        Integer b = pQ.poll();
        System.out.println("b = " + b); // 5

        Integer c = pQ.poll();
        System.out.println("c = " + c); // 4
    }
}

• PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder()); : PriorityQueue를 기본형(primitive type)으로 선언하고, Collections.reverseOrder()를 선언하면 가장 높은 숫자가 가장 먼저 꺼낼 수 있다.

Priority Queue를 이용하여 참조형 우선순위 사용법

객체의 우선순위는 Comparator 또는 Comparable 인터페이스를 구현하여 순위를 결정지을 수 있다.

class Lecture implements Comparable<Lecture> {
    int time;
    int money;

    public Lecture(int time, int money) {
        this.time = time;
        this.money = money;
    }

    @Override
    public int compareTo(Lecture o) {
        if (time == o.time) return o.money- money; // 금액이 높은 순
        return time - o.time; // 시간이 적은 순
    }
}
public class Ex01 {
    public static void main(String[] args) {
        PriorityQueue<Lecture> pQ = new PriorityQueue<>();
        pQ.offer(new Lecture(5, 10));
        pQ.offer(new Lecture(8, 40));
        pQ.offer(new Lecture(25, 30));
        pQ.offer(new Lecture(15, 80));
        pQ.offer(new Lecture(8, 60));

        Lecture l1 = pQ.poll();
        System.out.println("l1.time = " + l1.time + ", l1.money = " + l1.money);

        Lecture l2 = pQ.poll();
        System.out.println("l1.time = " + l2.time + ", l1.money = " + l2.money);

        Lecture l3 = pQ.poll();
        System.out.println("l1.time = " + l3.time + ", l1.money = " + l3.money);
    }
}

결과

l1.time = 5, l1.money = 10
l1.time = 8, l1.money = 60
l1.time = 8, l1.money = 40

Comparable 인터페이스를 이용하여 우선순위 기준을 정하였다.

1. 시간이 적은 강의가 우선순위가 높다.
2. 강의 시간이 같은 경우 금액이 높은 강의 우선순위가 높다.

References

• 쉬운코드 - 우선순위 큐
• https://coding-factory.tistory.com/603
• https://kbj96.tistory.com/49
• https://ko.wikipedia.org/wiki/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84_%ED%81%90