[Java] PriorityQueue

출처

ChatGPT

자바 8 소스코드

---

PriorityQueue는 자바의 큐(queue) 인터페이스를 구현한 클래스 중 하나로, 우선순위에 따라 요소들을 관리하는 큐이다. PriorityQueue는 힙(Heap) 자료구조를 기반으로 동작하며, 삽입된 요소들을 특정 우선순위에 따라 정렬하여, 가장 높은 우선순위를 가진 요소가 먼저 처리되도록 한다.

• 관련 글 -> [Java] Queue 인터페이스
• 관련 글 -> [자료 구조][Java] 힙 Heap

 

1. PriorityQueue의 주요 특징

우선순위 기반

PriorityQueue는 일반적인 큐와 달리, 요소들이 우선순위에 따라 정렬된다. 기본적으로 오름차순으로 정렬되며, Comparator를 제공하면 사용자 정의 우선순위로 정렬할 수 있다.

힙(Heap)  자료구조

내부적으로 이진 힙(Binary Heap) 자료구조를 사용해 요소를 저장하고 관리한다. 힙은 완전 이진 트리의 한 종료로, 트리에서 부모 노드가 자식 노드보다 우선순위가 높은 특징을 가진다. 이를 통해 O(log n)의 시간 복잡도로 삽입과 삭제가 이루어진다.

• 관련 글 -> [자료 구조]이진 힙 Binary Heap

정렬 순서

PrioriotyQueue는 큐의 정렬 순서를 명시적으로 보장하지 않는다. 즉, 요소들이 내부적으로는 정렬되지만, toString()이나 반복자를 통해 순회할 때는 순서가 보장되지 않는다. 다만, 큐의 첫 번째 요소는 항상 우선순위가 가장 높은 요소이다.

null 요소 허용 안 함

PriorityQueue는 null 요소를 허용하지 않는다. 이는 우선순위 비교시 null 값이 문제가 될 수 있기 때문이다.

 

2. PriorityQueue의 기본 동작

삽입 ( offer 또는 add() 메소드 )

큐에 요소를 삽입할 때, 해당 요소는 힙을 이용해 적절한 위치에 배치되어 우선순위를 유지한다. 삽입된 요소는 힙의 특성에 따라 부모 노드와 비교되어 적절한 위치로 올라가거나 내려간다.

제거 ( poll 메소드 )

큐에서 요소를 제거할 때, 가장 높은 우선순위를 가진 요소가 반환되고 제거된다. 힙에서 마지막 요소가 첫 번째 위치로 이동한 후, 다시 힙의 특성을 유지하기 위해 힙 다운(Heap Down) 작업이 진행된다.

조회 ( peek 메소드 )

큐의 맵 앞 요소(우선순위가 가장 높은 요소)를 반환하되, 큐에서 제거하지는 않는다.

 

3. PriorityQueue 메소드

1. 삽입 및 삭제

boolean offer(E e)

큐에 요소를 삽입하며, 성공적으로 삽입되면 true를 반환나다.

E poll

큐에서 우선순위가 가장 높은 요소를 제거하고 반환한다. 큐가 비어 있으면 null을 반환한다.

2. 조회

E peek()

큐의 첫 번째 요소(우선순위가 가장 높은 요소)를 반환하지만, 큐에서 제거하지는 않는다. 큐게 비어 있으면 null을 반환한다.

3. 기타 메소드

int size()

큐에 있는 요소의 개수를 반환한다.

boolean isEmpty()

큐가 비어 있는지 확인한다.

 

4. PriorityQueue의 내부 구현

PriorityQueue는 힙(Heap) 자료구조를 사용해 구현되면, 내부적으로 동적 배열(Object[])을 사용해 요소들을 저장한다. 힙은 완전 이진 트리로 구성되며, 최소 힙(min-heap) 또는 최대 힙(max-heap)으로 구현될 수 있다. PriorityQueue는 기본적으로 최소 힙으로 동작한다. 

1. 배열을 이용한 힙 구현

PriorityQueue는 배열을 사용해 트리 구조를 표현한다. 배열 인덱스를 사용해 부모와 자식간의 관계를 쉽게 계산할 수 있다.

• 부모 노드 인덱스 : (i-1) /2
• 왼쪽 자식 노드 인덱스 : 2 * i + 1
• 왼쪽 자식 노드 인덱스 : 2 * i + 1

2. 삽입 연산

PriorityQueue에 요소를 삽입할 때는 배열의 마지막에 요소를 삽입한 후, 힙 업(Heap Up) 작업을 통해 적절한 위치로 이동시킨다. 이느 부모 노드와 비교해 적절한 위치에 있을 때가지 반복된다.

 

자바 8 PriorityQueue 소스코드

/**
 * Inserts the specified element into this priority queue.
 * 
 * Returns:
 * true (as specified by Collection.add)
 * Throws: 
 * ClassCastException – if the specified element cannot be 
 * compared with elements currently in this priority queue 
 * according to the priority queue's ordering
 * Throws: 
 * NullPointerException – if the specified element is null
 */
public boolean add(E e) {
        return offer(e);
}

/**
 * Inserts the specified element into this priority queue.
 *
 * Returns:
 * true (as specified by Queue.offer)
 * Throws:
 * ClassCastException – if the specified element cannot be 
 * compared with elements currently in this priority queue 
 * according to the priority queue's ordering
 * Throws:
 * NullPointerException – if the specified element is null
 */
public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}



/**
 * Inserts item x at position k, maintaining heap invariant by 
 *  promoting x up the tree until it is greater than or equal to 
 *  its parent, or is the root. 
 *
 *  To simplify and speed up coercions and comparisons. the 
 *  Comparable and Comparator versions are separated into different 
 *  methods that are otherwise identical. (Similarly for siftDown.)
 *
 * Params:
 *  k – the position to fill
 *  x – the item to insert
 */
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

3. 삭제 연산

가장 높은 우선순위를 가진 요소(루트 노드)를 삭제할 때는 배열의 첫 번째 요소를 제거하고, 배열의 마지막 요소를 루트 위치로 이동시킨 후, 힙 다운(Heap Down) 작업을 수행해 힙의 특성을 유지한다.

@SuppressWarnings("unchecked")
public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);
    return result;
}

/**
 * Inserts item x at position k, maintaining heap invariant by 
 * demoting x down the tree repeatedly until it is less than or 
 * equal to its children or is a leaf.
 *
 * Params:
 * k – the position to fill
 * Params:
 *  x – the item to insert
 */
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

4. 확장 및 동적 배열 관리

PriorityQueue는 내부 배열이 가득 차면 자동으로 동적 배열 확장을 수행한다. 배열 크기는 기존 크기의 1.5배로 증가하며, 이는 Arrays.copyOf() 메소드를 사용해 새로운 배열로 복사된다.

/**
 * Increases the capacity of the array.
 *
 * Params:
 * minCapacity – the desired minimum capacity
 */
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

• 관련 글 -> [프로그래밍 개념] 동적 배열과 정적 배열

5. PriorityQueue의 예시

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 기본적으로 Integer 타입은 오름차순으로 정렬됨 (최소 힙)
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.offer(10);
        pq.offer(20);
        pq.offer(15);

        // 우선순위가 가장 높은 요소(10)를 반환하고 제거
        System.out.println("Poll: " + pq.poll()); // 출력: 10

        // 큐의 첫 번째 요소(15)를 조회하지만 제거하지 않음
        System.out.println("Peek: " + pq.peek()); // 출력: 15

        // 큐의 남은 요소들
        System.out.println("Remaining elements: " + pq); // 출력: [15, 20]
    }
}

 

6. Comparator를 사용한 PriorityQueue

PriorityQueue는 기본적으로 자연 순서(오름차순)로 요소를 정렬하지만, Comparator를 사용해 사용자 정의 정렬 기준을 적용할 수 있다. 예를 들어, 내림차순으로 정렬하는 PriorityQueue는 다음과 같이 구현할 수 있다.

• 관련 글 -> [Java] 자연 순서 Natural Ordering

import java.util.PriorityQueue;
import java.util.Comparator;

public class CustomPriorityQueueExample {
    public static void main(String[] args) {
        // 내림차순 정렬을 위한 Comparator를 사용한 PriorityQueue
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

        pq.offer(10);
        pq.offer(20);
        pq.offer(15);

        // 우선순위가 가장 높은 요소(20)를 반환하고 제거
        System.out.println("Poll: " + pq.poll()); // 출력: 20

        // 큐의 첫 번째 요소(15)를 조회하지만 제거하지 않음
        System.out.println("Peek: " + pq.peek()); // 출력: 15

        // 큐의 남은 요소들
        System.out.println("Remaining elements: " + pq); // 출력: [15, 10]
    }
}

 

7. PriorityQueue의 시간 복잡도

삽입 offer() : O(log n)

새로운 요소가 힙에 삽입될 때, 힙의 특성을 유지하기 위해 힙 업 (Heap Up) 작업이 수행된다.

삭제 poll() : O(log n)

루트 요소를 제거한 후, 마지막 요소가 루트로 이동하고 힙 다운 (Heap Down) 작업이 수행된다.

조회 peek() : O(1)

우선순위가 가장 높은 요소를 반환하는 작업은 힙에서 첫 번째 요소를 반환하므로 상수 시간에 이루어진다.

 

8. PriorityQueue의 단점

정렬된 순서로의 반복자 제공 안 함

PriorityQueue는 내부적으로 정렬되어 있지만, 큐의 요소를 순회할 때는 정렬된 순서로 제공되지 않는다. 따라서 큐를 순회하면서 우선순위에 따라 요소를 얻으려면, poll() 메소드를 반복 호출해야 한다.

null 허용 안 함

PriorityQueue는 null 값을 허용하지 않는다. null을 삽입하려고 하면 NullPointerException이 발생한다.