우선순위 큐(Priority Queue)

MMM·2023년 8월 14일

문제상황

우선순위 큐를 이용하는데, 조건 1(ex. 절대값)을 비교, 조건 1의 결과가 동일하다면 조건 2(ex. 음수/양수)를 비교해야 했다. 그래서 찾아본 우선순위 큐.

PriorityQueue

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable {
    private static final long serialVersionUID = -7720805057305804111L;
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    transient Object[] queue;
    int size;
    private final Comparator<? super E> comparator;
    transient int modCount;
    private static final int MAX_ARRAY_SIZE = 2147483639;

serializable, AbstractQueue를 동시에 상속하는 클래스.
기본 capacity는 11, 기본 comparator도 제공되지만 초기화 때 동시에 변경 가능하다.

`offer(E)`, `add(E)` : 값 추가

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

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

            this.siftUp(i, e);
            this.size = i + 1;
            return true;
        }
    }

Queue에 값 추가. 성공시 true, e가 null이면 NPE 발생.
add(E)는 그대로 offer(E)를 실행시키는 거라 처음부터 offer() 쓰는 게 나을 것 같다.
grow 부분 봤는데 현재 queue 길이가 64 미만이면 (기존길이 * 2 + 2), 아니면 (기존 길이 + 기존길이 >> 1)로 늘린다. 후자는 기존길이의 절반만큼 추가하는 셈. 그런데 전자는 왜 + 2를 추가로 해주는지 궁금. (chatGPT는 "작은 크기의 배열을 확장할 때 크기를 더 빠르게 증가시키기 위한 최적화 방법"이라고 답했다.)

참고) oldCapacity < 64일 때 newCapacity = oldCapacity * 2 + 2 해주는 이유에 관한 chatGPT의 답변

oldCapacity가 64 미만일 때 2를 곱한 후 2를 추가로 더해주는 이유는 작은 크기의 배열을 확장할 때 크기를 더 빠르게 증가시키기 위한 최적화 방법입니다. 작은 크기의 배열을 작은 단위로 계속해서 증가시키는 것은 메모리 낭비를 초래할 수 있으며, 작은 크기의 배열은 작은 작업에서도 빈번하게 확장되는 경우가 많기 때문에 이를 최적화하는 것이 목적입니다.

예를 들어, 배열의 크기가 작을 때 2를 곱한 후 2를 더하면, 크기가 작은 배열이 상대적으로 빠르게 커지게 됩니다. 작은 크기에서 작은 단위로 크기를 늘리는 대신, 비교적 더 큰 크기로 한 번에 늘리면 작은 크기에서 크기 변화에 따른 오버헤드를 줄일 수 있습니다.

이렇게 작은 크기의 배열을 더 빠르게 증가시키는 최적화 방법은 배열 크기 증가에 따른 성능 저하를 줄여주고 메모리 사용을 효율적으로 관리하는데 도움을 줄 수 있습니다.

`peek()` : 꼭대기값 반환

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

Queue의 제일 꼭대기값(=최소/최대값) 반환

`poll()` : 꼭대기값 삭제 및 반환

    public E poll() {
        Object[] es;
        Object result;
        if ((result = (es = this.queue)[0]) != null) {
            ++this.modCount;
            int n;
            E x = es[n = --this.size];
            es[n] = null;
            if (n > 0) {
                Comparator cmp;
                if ((cmp = this.comparator) == null) {
                    siftDownComparable(0, x, es, n);
                } else {
                    siftDownUsingComparator(0, x, es, n, cmp);
                }
            }
        }

        return result;
    }

Queue의 제일 꼭대기값 반환 & 삭제.

`indexOf(O)` : 인덱스 확인

    private int indexOf(Object o) {
        if (o != null) {
            Object[] es = this.queue;
            int i = 0;

            for(int n = this.size; i < n; ++i) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }

        return -1;
    }

다른 자료형의 indexOf()와 같지만 로직 보는 건 처음인 것 같아서 추가해둠. 어쩔 수 없이 for문 사용이긴 하구나 싶어서.

`remove(O)`, `removeEq(O)` : 값 삭제

    public boolean remove(Object o) {
        int i = this.indexOf(o);
        if (i == -1) {
            return false;
        } else {
            this.removeAt(i);
            return true;
        }
    }

    void removeEq(Object o) {
        Object[] es = this.queue;
        int i = 0;

        for(int n = this.size; i < n; ++i) {
            if (o == es[i]) {
                this.removeAt(i);
                break;
            }
        }

    }
    
    E removeAt(int i) {
        Object[] es = this.queue;
        ++this.modCount;
        int s = --this.size;
        if (s == i) {
            es[i] = null;
        } else {
            E moved = es[s];
            es[s] = null;
            this.siftDown(i, moved);
            if (es[i] == moved) {
                this.siftUp(i, moved);
                if (es[i] != moved) {
                    return moved;
                }
            }
        }

        return null;
    }

remove(O)는 equals를 이용해 매개변수의 인덱스를 찾아 삭제, removeEq(O)는 ==를 이용하여 매개변수의 인덱스를 찾아 삭제한다.

Comparator 수정

처음에 언급한 것 처럼 조건 1을 먼저 비교, 동일하다면 조건 2를 추가로 비교하게 해야했다. 고맙게도 백준에서 이런 문제를 제공하나보다. 관련해 참고하기 좋은 블로그를 발견했다.

PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
	int abs1 = Math.abs(o1);
	int abs2 = Math.abs(o2);

	if(abs1 == abs2) return o1 > o2 ? 1 : -1;
	return abs1 - abs2;
});