[Java]우선순위 큐(Priority Queue)에 대하여

우선순위 큐(Priority Queue)란?

큐의 모든 원소에 우선순위를 부여하여, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리되는 큐입니다.

 

우선순위 큐에 대해서 잘못 알려진 사실

우선순위 큐가 힙은 같다고 생각하는 분들이 많으나, 우선순위큐는 다른 추상 자료형처럼 추상적인 개념이며 힙이 아닙니다.

힙은 우선순위큐를 구현하는 여러 방법 중 보편적으로 많이 사용되는 자료구조입니다. 해당 글에서는 우선순위큐를 힙으로 구현한다고 가정하고 설명을 진행하도록 하겠습니다.

 

우선순위를 비교하는 방법

원소의 우선순위를 비교하여 주는 Comparator를 사용하여 비교하거나 원소에 Comparable 인터페이스 구현을 사용하여 비교합니다.

    /**
     * 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.)
     *
     * @param k the position to fill
     * @param x the item to insert
     */
    private void siftUp(int k, E x) {
        if (comparator != null) // Comparator을 전달받지 않은 경우
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }
    
    /**
     * 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.
     *
     * @param k the position to fill
     * @param x the item to insert
     */
    private void siftDown(int k, E x) {
        if (comparator != null) // Comparator을 전달받지 않은 경우
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

 

짤막 siftUp, siftDown 메서드란 무엇인가

siftUp, siftDown 메서드는 우선순위 큐를 구현한 힙을 원소의 우선순위에 맞게 위 방향 또는 아래 방향으로 재구축하여 주는 메서드입니다.

 

Comparator을 사용하는 방법

원소에 Comparable 인터페이스를 정의할 수 없거나, 정의된 우선순위 비교 방법을 사용하고 싶지 않은 경우(정의된 방법을 수정하지 못하는 경우 등)는 우선순위 비교를 위한 Comparator을 사용할 수 있습니다.

 

Comparator는 우선순위큐를 생성할 때 생성자를 통하여 전달할 수 있습니다.

public class App {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        pq.offer(1);
        pq.offer(4);

        while(!pq.isEmpty()) {
            System.out.println(pq.poll()); // 결과 : 4, 1
        }
    }
}

 

우선순위 큐를 생성할 때 Comparator.reversedOrder Comparator을 전달하여 주었습니다. 해당 Comparator을 사용하여 우선순위

를 비교, 결과적으로 우선순위가 높은(여기서는 숫자가 큰) 원소가 먼저 제거되어 반환되는 것을 확인할 수 있습니다.

 

Comparable 인터페이스 구현

우선순위 큐를 생성할 때 Comparator을 전달하지 않을 경우는 삽입하는 원소는 반드시 Comparable 인터페이스를 구현하여야 합니다. 기본자료형의 래퍼 클래스의 경우는 모두 Comparable 인터페이스가 구현되어있습니다.

public class App {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        // 위 우선순위큐는 객체(원소)에 정의된 방법에 따라 비교됩니다. - 최소힙
        // 최대힙으로 동작하길 원한다면 new PriorityQueue<>(Comparator.reverseOrder());
        pq.offer(1);
        pq.offer(4);

        while(!pq.isEmpty()) {
            System.out.println(pq.poll()); // 결과 : 1, 4
        }
    }
}

 

기본자료형에 구현된 Comparable 인터페이스에 의하여 우선순위가 낮은(여기서는 숫자가 작은) 원소가 먼저 제거되어 반환되는 것을 확인할 수 있습니다.

 

만약 원소가 Comparable 인터페이스를 구현하지 않았다면?

만약 아래와 같이 우선순위 큐에 삽입하는 원소가 Comparable 인터페이스를 구현하지 않았다면 어떤 일이 벌어질까요?

class Student {

}

public class App {
    public static void main(String[] args) {
        PriorityQueue<Student> pq = new PriorityQueue<>();
        pq.offer(new Student());
        pq.offer(new Student()); 
        // Exception in thread "main" java.lang.ClassCastException: 
        // com.study.Student cannot be cast to java.lang.Comparable
    }
}

 

Comparator을 별도로 전달하지 않았으므로 우선순위 큐는 우선순위 비교를 위하여 원소가 구현한 Comparable 인터페이스를 이용하려고 시도합니다.

@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
  Comparable<? super E> key = (Comparable<? super E>) x; // Comparable 인터페이스로 캐스팅 시도
  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;
}

@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
  Comparable<? super E> key = (Comparable<? super E>)x; // Comparable 인터페이스로 캐스팅 시도
  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;
}

 

즉 원소를 Comparable 인터페이스로 캐스팅을 하게 되는데, 구현을 하지 않았다면 캐스팅에 실패하여 ClassCastException이 발생합니다.

 

주로 사용하는 메서드

아래는 우선순위 큐에서 주로 사용하는 메서드만을 나열해 본 것입니다.

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

	public PriorityQueue();
	public PriorityQueue(Comparator<? super E> comparator);
	public boolean offer(E e);
	public E poll();
	public E peek();
	public int size();
	public void clear();
	public boolean isEmpty();
}

 

0-1. 기본 생성자

    /**
     * Creates a {@code PriorityQueue} with the default initial
     * capacity (11) that orders its elements according to their
     * {@linkplain Comparable natural ordering}.
     */
    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

 

0-2. Comparator 지정 생성자

    /**
     * Creates a {@code PriorityQueue} with the default initial capacity and
     * whose elements are ordered according to the specified comparator.
     *
     * @param  comparator the comparator that will be used to order this
     *         priority queue.  If {@code null}, the {@linkplain Comparable
     *         natural ordering} of the elements will be used.
     * @since 1.8
     */
    public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

 

1. offer 메서드

우선순위큐에 원소를 삽입하는 메서드입니다.

public class App {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(1);
        pq.offer(2);
        System.out.println(pq); // 결과 : [1, 2]
    }
}

 

2. poll 메서드

우선순위 큐의 머리 부분의 원소를 제거한 후 해당 원소를 반환하여 줍니다.

만약 우선순위 큐가 비어있을 경우 null을 반환하여 줍니다.

public class App {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(1);
        System.out.println(pq.poll()); // 결과 : 1
        System.out.println(pq.poll()); // 결과 : null
    }
}

 

첫 poll 메서드 호출 시, 우선순위 큐의 머리 부분의 원소 1을 제거한 후 반환하여줍니다.

두 번째 poll 메서드 호출 시, 우선순위 큐가 비어있으므로 null을 반환하여 줍니다.

 

3. peek 메서드

우선순위 큐의 머리 부분의 원소를 제거하지 않고 해당 원소를 반환하여 줍니다.

만약 우선순위 큐가 비어있을 경우 null을 반환하여 줍니다.

public class App {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(1);
        System.out.println(pq.peek()); // 결과 : 1
        System.out.println(pq.poll()); // 결과 : 1
    }
}

 

peek 메서드 호출 시, 우선순위 큐의 머리 부분의 원소 1을 제거하지 않고 반환하여 줍니다.

poll 메서드 호출 시 우선순위 큐가 비어있지 않아 null이 아닌 머리 부분의 원소 1을 제거하고 반환하여 줍니다.

 

4. size 메서드

우선순위 큐에 존재하는 원소의 개수를 반환하여 줍니다.

public class App {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(1);
        pq.offer(2);
        System.out.println(pq.size()); // 결과 : 2
    }
}

 

offer 메서드로 총 2개의 원소를 우선순위큐에 삽입하였으므로,

size 메서드 호출 시 우선순위큐에 존재하는 원소의 개수인 2를 반환하여  줍니다.

 

5.  clear 메서드

우선순위큐에 존재하는 모든 원소를 삭제합니다.

public class App {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(1);
        pq.offer(2);
        pq.clear();
        System.out.println(pq.size()); // 결과 : 0
    }
}

 

clear 메서드를 호출하여 우선순위큐에 존재하는 모든 원소가 삭제되었으므로,

size 메서드 호출 시 우선순위큐에 존재하는 원소의 개수인 0을 반환하여 줍니다.

 

6. isEmpty 메서드

우선순위큐에 원소가 존재하지 않는다면 true를, 존재한다면 false를 반환하여 줍니다.

public class App {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(1);
        pq.offer(2);
        System.out.println(pq.isEmpty()); // 결과 : false
        pq.clear();
        System.out.println(pq.isEmpty()); // 결과 : true
    }
}

 

첫 isEmpty 메서드 호출 시 우선순위 큐에는 총 2개의 원소가 존재하므로 false를,

두 번째 isEmpty 메서드 호출 시 우선순위큐에는 원소가 존재하지 않으므로 true를 반환하여 줍니다.