[자료구조] 우선순위 큐(Priority Queue)

  우선순위 큐(Priority Queue)란 가장 높은 우선순위를 가진 항목에 접근하거나 삭제하는 연산과 임의의 우선순위를 가진 항목을 삽입하는 연산을 지원하는 자료구조입니다. 스택이나 큐도 일종의 우선순위 큐로, 스택의 경우 가장 마지막으로 삽입된 항목이 가장 높은 우선순위를 가지며, 최근 시간일수록 높은 우선순위를 부여하는 우선순위 큐입니다. 큐의 경우 먼저 삽입된 항목이 우선순위가 더 높습니다. 따라서 이른 시간일수록 더 높은 우선순위를 부여하는 우선순위 큐입니다.

  우선순위 큐는 배열, 연결 리스트, 힙을 이용하여 구현할 수 있습니다. 정렬된 배열과 연결 리스트에서의 삽입과 삭제의 시간 복잡도는 각각 O(N)과 O(1)입니다. 그러나 힙의 경우에는 각각 O(logN)이므로 일반적으로는 힙 자료구조가 가장 효율적이며, 자바에서의 우선순위 큐 클래스 역시 힙으로 구현되어 있습니다. 힙으로 구현했을 때  삽입과 삭제 과정은 최소 힙 및 최대 힙과 동일합니다.

 

  우선순위 큐 구현 코드

import java.util.PriorityQueue;
class Person {
    String name;
    int age;
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}
public class Main {
    public static void solution(String[] name, int[] age) {
        PriorityQueue<Person> pq = new PriorityQueue<>();
    }
    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> pq2 = new PriorityQueue<>(
                (Person p1, Person p2) -> p1.age >= p2.age ? 1 : -1);
        for (int i = 0; i < name.length; i++) {
            pq2.offer(new Person(name[i], age[i]));

        }
    }
}

  위 코드는 우선순위 큐를 구현한 예시입니다. 구현 시 객체의 값을 어떤 기준으로 우선순위를 구성할 것인지 지정해주어야 합니다. Comparable 인터페이스로 확장하여 CompareTo를 오버라이드 하는 방법과, 위 코드와 같이 생성 시 인자에 비교 기준을 지정하는 방법이 있습니다. 위 코드는 람다식과 삼항 연산자를 활용했습니다.

  우선순위 큐를 구현하는 자료구조에는 이진 힙 이외에도 다양한 종류가 있습니다. Leftist 힙, Skew 힙, 이항 힙(Binomial Heap), 피보나치 힙(Fibonacci Heap) 등을 예로 들 수 있습니다.

 

  ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.