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

우선순위 큐(Priority Queue)

Priority Queue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서,

데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이며, 힙(Heap)이라고도 부른다.

 

• 일반적인 큐의 구조 FIFO (First In First Out)을 가진다.
• 우선순위를 먼저 결정하고, 우선순위가 높은 데이터가 먼저 나가는 구조이다.
• Heap을 이용하여 구현하는 것이 일반적이다.
• 데이터 추출 시, 루트 노드를 얻어 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입 후 아래 노드로 내려가면서 정렬하는 방식으로 진행된다.
• 최대 힙 = 최대 값이 우선순위인 큐 
• 최소 힙 = 최소 값이 우선순위인 큐

 

Heap 자료구조 Tree 형태로 보기

 

 

Heap 자료구조 배열로 보기

 

위의 그림에서 보이듯이 숫자가 클수록 우선순위가 높게 저장되어 있는데 이런 형태를 최대 힙(Max Heap)이라고 부른다. 정렬 상태를 보면 알겠지만 높은 층위에 있는 숫자가 더 크다. 즉, 자식 노드보다 부모 노드가 더 큰 숫자를 갖고 있다.

이를 배열 형태로 늘어서 보면 1번 노드부터 10번 노드까지 Index에 순서대로 넣는 형태가 된다.

 

일반적으로 우선순위 큐는 0번 Index는 사용하지 않는다.

 트리 구조의 특성에 따른 것으로, Index 값을 좌측 자식은 부모 노드의 x2, 우측 자식은 부모 노드의 x2 + 1로 설정하고 부모 노드는 자식 노드 아무 쪽에서든, 1/2을 곱해주면 바로 구할 수 있기 때문이다.

 

우선 순위 큐 기본동작 

• enqueue()- queue에 새 요소를 삽입한다.
• dequeue() - queue에서 최대 우선순위 요소를 삭제하고 그 값을 반환한다.
• peek() - queue에서 최대 우선순위 요소를 반환한다.

 

우선순위 큐(Heap) 특징 및 시간 복잡도

특징

 

• 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조이다.
  • 우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야 한다.
• 완전 이진트리 구조의 형태를 갖는다.
• 일반적으로 배열로 구현한다.
• 일종의 반 정렬 상태를 유지한다.(느슨한 정렬 상태)
• 우선순위를 중요시해야 하는 상황에 사용

 

우선순위 큐를 구현하는 데 있어 데이터 삽입, 추출 시간복잡도

우선순위 큐는 배열에 저장하되 삽입/ 추출 시 기존 정렬 상태를 유지하기에 O(logn)의 시간복잡도를 유지한다. 

 

우선순위 큐 동작 

우선순위 큐를 사용하기 위해 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야 한다.

Comaprable Interface 구현 시 compareTo method를 override 하여 처리할 우선순위 조건을 리턴하면, 우선순위 큐가 우선순위가 높은 객체를 추출해 준다. (기본적으로 낮은 숫자부터 큰 숫자 오름차순이다.)

 

ex) 백준 2109번 순회강연 https://www.acmicpc.net/problem/2109

 

해당 문제는 그리디 알고리즘 문제로 순간마다 최선이라고 생각하는 방향으로 결정하는 방식의 알고리즘이다.

같은 날에 두 강연이 있다면 더 비싼 강연료를 받는 것이 최선이다. 

그렇기에 트리구조인 우선순위 큐(heap)를 활용해서 해당 문제를 해결할 수 있다.

첫 번째 기준은 강연료가 높은 순서로 우선순위를 두었고,

두 번째 기준으로는 같은 강연료일 경우 날짜 제한이 빠른 강연을 우선순위에 두었다.

 

 

PriortyQueue에서 하나씩 꺼내준다.

강연료는 100이고 날짜 제한은 2일까지이다. 그러면 2일째부터 역순으로(2일 -> 1일) check 배열을 체크하며 

2일에 check 배열을 트루로 바꾸고 해당 값을 저장한다.

이런 식으로 모든 PriorityQueue 안의 강연이 (큐가 빌 때까지 ) 없어질 때까지 반복한다.

 

만약 어떤 강연을 꺼냈는데, 날짜 제한을 역순으로 체크해 보아도 비어있는 날짜가 없다면, 그 강연은 받을 수 없게 된다.

-> 날짜가 같은경우 중 강연료가 높은 순서를 우선순위로 두어 true 값으로 check 배열을 체크하기 때문

문제에서 주어진 테스트 케이스에 대해서 loop를 수행한 결과는 아래와 같다.

 

 

 자바 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static class lecture {
        int p;
        int d;

        public lecture(int p, int d) {
            this.p = p;
            this.d = d;
        }
    }

    public static int n;
    public static boolean[] check;

    public static PriorityQueue<lecture> queue = new PriorityQueue<>((o1, o2) -> {
        if (o1.p == o2.p) {
            return o1.d - o2.d;
        }
        return o2.p - o1.p;
    });

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        check = new boolean[10001];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            queue.offer(new lecture(A, B));
        }

        int sum = 0;
        while (!queue.isEmpty()) {
            lecture cur = queue.poll();
            for (int i = cur.d; i > 0; --i) {
                if (!check[i]) {
                    check[i] = true;
                    sum += cur.p;
                    break;
                }
            }
        }

        System.out.println(sum);
    }
}