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

Priority Queue (우선순위 큐)

---

1. Priority Queue (우선순위 큐)

일반적인 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로,
스택과는 다르게 FIFO(First In First Out)의 구조를 가진다.
Priority Queue는 큐와는 다르게 우선순위를 결정하고
우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

Priority Queue는 요소가 처리되는 순서가 중요한 결과를 가져올 수
있는 실시간 시스템에서 자주 사용된다. 또한 그래프에서 최단 경로를 찾는
Dijkstra Algorithm(다익스트라 알고리즘)과 경로 찾기를 위한
A* Algorithm(에이스타 알고리즘)과 같은 알고리즘에 사용된다.

1.1 Priority Queue의 특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조
   우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야한다.
2. 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있다.
3. 따라서 시간 복잡도는 O(NLogN)

2. Priority Queue 구현

Priority Queue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로
Comparable Interface를 구현해야 한다.
Comparable Interface를 구현하면 compareTo method를 override 하게 되고
해당 객체에서 처리할 우선순위 조건을 리턴해주면 Priority Queue가 알아서 우선순위가
높은 객체를 추출 작업 해준다.

2.1 Priority Queue 선언

Priority Queue를 사용하려면 java.util.PriorityQueue를 import 해야한다.

import java.util.PriorityQueue;

// 낮은 숫자가 우선 순위인 int형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

// 높은 숫자가 우선 순위인 int형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

2.2 Priority Queue 기능

Priority Queue 값 추가

priorityQueueLowest.add(1);
priorityQueueLowest.add(10);
priorityQueueLowest.offer(100);

priorityQueueHighest.add(1);
priorityQueueHighest.add(10);
priorityQueueHighest.offer(100);

우선순위 큐에 값을 추가하고 싶다면 add(value) 또는 offer(value)
method를 활용하면 된다. 만약 삽입에 성공하면 true를 return하고, 큐에
여유 공간이 없어 실패하면 IllegalStateException을 발생 시킨다.
우선순위 큐에 값을 추가하면 아래와 같은 구조로 이루어진다.

Priority Queue 값 삭제

// priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueueLowest.poll(); 

// priorityQueue에 첫번째 값 제거. 비어있다면 예외 발생
priorityQueueLowest.remove(); 

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 null을 반환
priorityQueueLowest.peek();

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 예외 발생
priorityQueueLowest.element();

// 초기화
priorityQueueLowest.clear();

우선순위 큐에서 값을 제거하고 싶다면 poll()또는 remove() method를
활용하면 된다. 우선순위 큐에서 값 삭제는 아래와 같은 구조로 이루어진다.

3. Priority Queue 예제

import java.util.PriorityQueue;
import java.util.Collections;

class Bass implements Comparable<Bass> {
    private int price;
    private String brand;

    public Bass(int price, String brand) {
        this.price = price;
        this.brand = brand;
    }

    public int getPrice() {
        return this.price;
    }

    public String getBrand() {
        return this.brand;
    }

    @Override
    public int compareTo(Bass bass) {
        if (this.price > bass.getPrice()) {
            return 1;
        } else if (this.price < bass.getPrice()){
            return -1;
        }
        return 0;
    }
}

public class PriorityQueueT {
    public static void main(String[] args) {
        PriorityQueue<Bass> priorityQueue = new PriorityQueue<>();

        priorityQueue.add(new Bass(30, "Swing"));
        priorityQueue.add(new Bass(20, "Cort"));
        priorityQueue.add(new Bass(80, "Yamaha"));
        priorityQueue.add(new Bass(150, "Fender"));

        while (!priorityQueue.isEmpty()) {
            Bass bass = priorityQueue.poll();
            System.out.println("가격 : " + bass.getPrice() + "만원 / 브랜드명 : " + bass.getBrand());
        }
    }
}

/* result
가격 : 20만원 / 브랜드명 : Cort
가격 : 30만원 / 브랜드명 : Swing
가격 : 80만원 / 브랜드명 : Yamaha
가격 : 150만원 / 브랜드명 : Fender
*/

---

참고
programiz
geeksforgeeks
코딩팩토리
gillog