PriorityQueue

PriorityQueue

PriorityQueue 란 우선순위 큐로써 일반적인 큐의 구조 FIFO를 가지면서

데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고, 그 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다.

 

쉽게 말해서, 데이터를 큐에 추가하면 우선순위대로 정렬하고, 우선순위가 높은 데이터가 가장 먼저 나가는 것입니다.

 

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

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

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

 

클래스 코드

java.util.PriorityQueue;

 

생성자

public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

PrioriryQueue선언 시 구현한 Comparator로 정렬 기준을 지정할 수 있습니다.

 

데이터 추가

public boolean add(E e) {
    return offer(e);
}

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    siftUp(i, e);
    size = i + 1;
    return true;
}

add 메서드를 호출하면 offer 메서드가 호출하고, 큐의 길이를 증가시킵니다. (grow)

내부 정렬 로직과 데이터를 추가하는 메서드는 siftUp 메서드가 수행할 거라 예상됩니다.

 

정렬

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x, queue, comparator);
    else
        siftUpComparable(k, x, queue);
}

private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (key.compareTo((T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = key;
}

private static <T> void siftUpUsingComparator(
    int k, T x, Object[] es, Comparator<? super T> cmp) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (cmp.compare(x, (T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = x;
}

Comparator 사용 시 siftUpUsingComparaotr, 미사용 시 siftUpComparable 메서드를 호출합니다.

 

siftUpComparable의 내부 로직을 보면, 기본 Comparable(오름차순)을 사용하여 정렬하고 있습니다.

1. 추가하려는 데이터를 기존의 큐의 마지막 요소부터 검사를 합니다. (루프)

2. 추가하려는 데이터가 요소보다 크거나 같으면 해당 위치에 데이터를 추가합니다.

 

데이터를 추가할 때, 우선순위에 따라 비교하므로 정렬된 상태를 유지한다는 것을 알 수 있습니다.

 

데이터 추출

public E peek() {
    return (E) queue[0];
}

peek 메서드는 우선순위가 가장 높은 첫번째 원소를 추출합니다.

오름차순으로 정렬 시 가장 작은 원소를 반환합니다.

 

public E poll() {
    final Object[] es;
    final E result;

    if ((result = (E) ((es = queue)[0])) != null) {
        modCount++;
        final int n;
        final E x = (E) es[(n = --size)];
        es[n] = null;
        if (n > 0) {
            final Comparator<? super E> cmp;
            if ((cmp = comparator) == null)
                siftDownComparable(0, x, es, n);
            else
                siftDownUsingComparator(0, x, es, n, cmp);
        }
    }
    return result;
}

poll 메서드는 우선순위가 가장 높은 첫번째 원소를 추출하고, 큐에서 제거합니다.

 

참고 자료

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90