[선형] Priority Queue

❒ Description

---

우선순위 큐(Priority Queue)에 대해서 알아보자.

 

 

 

❒ Priority Queue

---

우선순위 큐(Priority Queue)는 스택과 큐와 같은 추상자료형(ADT)이다.

Queue와 거의 비슷하지만, 각 요소들이 우선순위를 갖고 있다는 차이점이 있다.

 

---

 

P-Queue는 여러가지 자료구조로 구현이 가능하다.

위와 같이 여러 구현 방식이 있지만, 최악의 경우에도 시간복잡도가 O(logN)인 'Heap(힙)' 자료구조를

활용하는 방식이 가장 대표적이다.

 

 

 

❒ Java에서 Priority Queue 선언하기

---

기본적으로 아래와 같이 P-Queue를 선언한다. 이 경우는 작은 숫자가 우선순위를 가지는 P-Queue이다.

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

 

---

 

커스텀으로 비교를 하고 싶으면 아래와 같이 사용할 수 있다.

PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> {
    if (o1.val == o2.val) {
        return 0;
    } else if (o1.val > o2.val) {
        return 1;
    } else {
        return -1;
    }
});

Compartor를 사용하여 특정 기준으로 우선순위를 부여할 수 있다.