주니어 백엔드 개발자 인터뷰

# 우선순위 큐 (Priority Queue)

정의

우선순위 큐는 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료구조입니다.

image

  • 모든 항목에는 우선순위가 있습니다.
  • 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 제외됩니다.
  • 두 요소의 우선 순위가 같은면 queue의 순서에 따라 제공됩니다.
  • 우선순위 큐는 힙을 기반으로 구현됩니다.
  • 시뮬레이션 시스템, 네트워크 트래픽 제어, OS에서 작업의 스케쥴링 등에 사용됩니다.

# 데이터 삽입&삭제 시간복잡도

image

  • 배열, 연결 리스트, 힙으로 구현 가능하지만 힙을 이용하는 것이 가장 효율적입니다.
  • 힙을 이용한 구현이 이루어지기에 O(logN) 입니다.

# 자바에서의 우선순위 큐

image

  • 일반적인 큐를 사용하는 것처럼 add(), peek(), poll() 등의 메소드를 사용할 수 있습니다.
  • PriorityQueue는 동기화 되어있지 않기 때문에 동기화가 필요하다면, PriorityBlockingQueue를 사용해야 합니다.
import java.util.PriorityQueue;

 public class Sample {
    public static void main(String[] args) {
        // 우선순위 큐 생성
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        // 우선순위 큐에 값 삽입
        pq.add(4);
        pq.offer(1);
        
        // 우선순위 큐에서 값을 꺼내기
        pq.poll(); // 1이 출력된다.
    }
}
  • add() 대신 offer() 메소드를 사용해도 동일한 결과가 산출됩니다.
  • 이외의 로직들은 Queue의 기본적인 기능과 유사하기에 생략하도록 하겠습니다.

# 우선순위 큐의 우선순위를 지정하기

  • 위의 예제는 정렬이 쉽게 가능한 정수 자료형이었기에, 따로 우선순위를 지정하지 않았습니다.
  • 만약에 순서를 직접 정의하여 정렬을 하고 싶다면 어떨까요?
class Student implements Comparable<Student> {
	int age;
	int classNumber;
	
	@Override
	public int compareTo(Student o) {
		return this.age - o.age;
	}
}
  • 위처럼 Comparable 인터페이스를 이용하여 객체 자체에 대한 비교 방법을 미리 구현해두면, 기본 생성자로 생성시 원하는 순서대로 정렬됩니다.

image

  • 우선순위 큐에서 제공하는 생성자 중에, 우선순위를 Comparator 클래스로 받는 생성자가 존재합니다.
  • 따라서 Comprator를 생성할 때 넘겨줌으로써 정렬 순서를 지정해주는 방법이 있습니다.
// Collections에서 제공하는 Comparator
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

// 직접 구현하는 Comparator
PriorityQueue<Student> pq = new PriorityQueue<>(new Comparator<Student>() {
    @Override
    public int compare(Student p1, Student p2) {
       return p1.age >= p2.age ? 1 : -1;
    }
});

# 참고자료

← 그래프(Graph) →