[자료구조/알고리즘] 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

• 정의
  우선순위가 높은 데이터가 먼저 나오는 자료구조($\neq$ FIFO)
• 특징
  모든 데이터에 우선순위가 존재
  Dequeue 시 우선순위가 높은 순서로 나감
  우선 순위가 서로 같은 경우 FIFO
  힙 자료구조와 동일한 방식으로 동작
  

자료구조별 시간복잡도

	enqueue	dequeue
정렬된 배열	O(N)	O(1)
정렬된 리스트	O(N)	O(1)
정렬되지 않은 배열	O(1)	O(N)
정렬되지 않은 리스트	O(1)	O(N)
힙	O(logN)	O(logN)

자바에서 재공하는 우선순위 큐는 내부적으로 Heap으로 구현되어 있음

구현

우선순위 큐의 구현은 힙과 동일하기 때문에 자바 기본 메서드의 사용 방법 위주로 구현

• 자바의 우선순위 큐의 경우 기본적으로 오름차순 정렬

1. 우선순위를 가진 노드를 큐에 추가하는 경우

class PriorityNode {
    int data;
    int priority;

    public PriorityNode(int data, int priority) {
        this.data = data;
        this.priority = priority;
    }
}

public class Main {
    public static void main(String[] args) {
        // -1: 변경
        //  1: 유지
        PriorityQueue<PriorityNode> pq1 = new PriorityQueue<>(
                (PriorityNode p1, PriorityNode p2) -> p1.priority >= p2.priority ? 1 : -1 // 오름차순
        );
        PriorityQueue<PriorityNode> pq2 = new PriorityQueue<>(
                (PriorityNode p1, PriorityNode p2) -> p1.priority >= p2.priority ? -1 : 1 // 내림차순
        );

        int data = 10;
        for (int i = 1; i < 5; i++) {
            pq1.add(new PriorityNode(data++, i));
            pq2.add(new PriorityNode(data++, i));
        }

        System.out.println("====오름차순====");
        while (!pq1.isEmpty()) {
            PriorityNode node = pq1.poll();
            System.out.println("priority: " + node.priority + " " + "data: " + node.data);
        }

        System.out.println("====내림차순====");
        while (!pq2.isEmpty()) {
            PriorityNode node = pq2.poll();
            System.out.println("priority: " + node.priority + " " + "data: " + node.data);
        }
    }
}

2. 정수타입 인자를 큐에 추가하는 경우

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq1 = new PriorityQueue<>();
        pq1.add(1);
        pq1.add(2);
        pq1.add(3);
        pq1.add(4);
        System.out.println(Arrays.toString(pq1.toArray());
        
        PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순
		pq2.add(1);
        pq2.add(2);
        pq2.add(3);
        pq2.add(4);
        System.out.println(Arrays.toString(pq1.toArray());