[Java] 우선순위 큐(Priority Queue) 개념과 자바 기본 메소드

우선순위 큐(Priority Queue)

일반적인 큐의 구조는 FIFO(Firtst In First Out)로 데이터가 들어온 순서대로 나가게 됩니다.

우선순위 큐는 이러한 큐의 특성을 가지면서 들어온 순서대로가 아니라

우선순위를 먼저 결정하고, 그 우선순위가 높은 데이터가 먼저 나가는 자료 구조입니다.

 

일반적으로 힙(Heap)을 이용하여 구현합니다.

힙은 항상 최대값 또는 최소값을 빠르게 찾아내기 위한 완전 이진 트리 구조입니다.

최대값 혹은 최소값으로 가장 먼저 탐색해야 하는 요소, 즉 우선순위가 가장 높은 요소가 루트 노드에 있습니다. 

부모 노드가 항상 자식 노드보다 우선순위가 높은 거죠.

 

새로운 데이터를 리프 노드에 넣고, 루트(가장 우선순위 높은 데이터)를 제거하면 우선순위 큐로 사용할 수 있습니다.

우선적으로 삭제할 노드 하나는 늘 루트에 있으면서, 내부는 정렬되어 있지 않습니다. 꺼낼 때마다 우선적으로 꺼낼 요소 하나가 정해집니다.

 

최댓값을 최우선으로 하고 싶다면 최대 힙(Max Heap)을, 최솟값을 최우선으로 하고 싶다면 최소 힙(Min Heap)을 사용하면 됩니다.

 

힙으로 우선순위 큐를 구현할 경우, 시간복잡도는 다음과 같습니다.

• 우선순위가 가장 높은 값을 탐색하는 시간은 O(1)
• 데이터를 삽입하는 시간은 O(logN)
• 데이터를 삭제하는 시간은 O(logN)

---

Java에서 사용하기

Import와 선언

`PriorityQueue`를 사용하기 위해서는 `java.util.PriorityQueue`를 import해야 합니다.

기본적으로 최소 힙(오름차순)으로 구현되어 있습니다.

 

만약 최대 힙(내림차순)으로 사용하고 싶다면 `Collections.reverseOrder()`이 필요합니다.

 

일반적으로 코딩테스트에서는 `java.util.*` 로 util 패키지를 전체 import하니 따로 Collections까지 외울 필요는 없을 듯 합니다.

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

public class Main{

  public static void main(String[] args) {
    // 최소 힙으로 구현한 우선순위 큐
    PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();
    
    // 최대 힙으로 구현한 우선순위 큐
    PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());
  }
}

주요 메서드

`public boolean add(E e)`	큐에 요소 삽입, 공간 부족 시 예외 발생
`public boolean offer(E e)`	큐에 요소 삽입, 공간 부족 시 false 반환
`public E peek()`	가장 우선순위 높은 요소 확인 (삭제 X)
`public E poll()`	가장 우선순위 높은 요소 꺼내기 (삭제 O)
`public boolean remove(Object o)`	특정 요소 제거
`public boolean isEmpty()`	큐가 비었는지 확인
`public int size()`	전체 원소 개수 확인
`public void clear()`	큐 비우기

전체 코드

import java.util.PriorityQueue;

public class Main{

  public static void main(String[] args) {
    // 최소 힙으로 구현한 우선순위 큐
    PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

    priorityQueueLowest.offer(5);
    priorityQueueLowest.offer(4);
    priorityQueueLowest.offer(2);
    priorityQueueLowest.offer(1);
    priorityQueueLowest.offer(3);

    System.out.println("현재 최소 힙 큐의 루트 = " + priorityQueueLowest.peek());
    System.out.println("삭제1, 삭제된 원소 = " + priorityQueueLowest.poll());
    System.out.println("현재 최소 힙 큐의 루트 = " + priorityQueueLowest.peek());
    System.out.println("삭제2, 삭제된 원소 = " + priorityQueueLowest.poll());
    System.out.println("현재 최소 힙 큐의 루트 = " + priorityQueueLowest.peek());
    System.out.println("삭제3, 삭제된 원소 = " + priorityQueueLowest.poll());
    System.out.println("현재 최소 힙 큐의 루트 = " + priorityQueueLowest.peek());
    System.out.println("삭제4, 삭제된 원소 = " + priorityQueueLowest.poll());
    System.out.println("현재 최소 힙 큐의 루트 = " + priorityQueueLowest.peek());
    System.out.println("삭제5, 삭제된 원소 = " + priorityQueueLowest.poll());

    if (priorityQueueLowest.isEmpty()) {
      System.out.println("최소 힙 큐가 비었습니다.");
    } else {
      System.out.println("최소 힙 큐에 아직 " + priorityQueueLowest.size() + "개의 원소가 있습니다.");
    }

  }
}

출력 // 1, 2, 3, 4, 5 작은 순서대로 삭제됨 현재 최소 힙 큐의 루트 = 1 삭제1, 삭제된 원소 = 1 현재 최소 힙 큐의 루트 = 2 삭제2, 삭제된 원소 = 2 현재 최소 힙 큐의 루트 = 3 삭제3, 삭제된 원소 = 3 현재 최소 힙 큐의 루트 = 4 삭제4, 삭제된 원소 = 4 현재 최소 힙 큐의 루트 = 5 삭제5, 삭제된 원소 = 5 최소 힙 큐가 비었습니다.

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

public class Main{

  public static void main(String[] args) {

    // 최대 힙으로 구현한 우선순위 큐
    PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

    priorityQueueHighest.offer(2);
    priorityQueueHighest.offer(4);
    priorityQueueHighest.offer(5);
    priorityQueueHighest.offer(3);
    priorityQueueHighest.offer(1);

    System.out.println("현재 최대 힙 큐의 루트 = " + priorityQueueHighest.peek());
    System.out.println("삭제1, 삭제된 원소 = " + priorityQueueHighest.poll());
    System.out.println("현재 최대 힙 큐의 루트 = " + priorityQueueHighest.peek());
    System.out.println("삭제2, 삭제된 원소 = " + priorityQueueHighest.poll());
    System.out.println("현재 최대 힙 큐의 루트 = " + priorityQueueHighest.peek());
    System.out.println("삭제3, 삭제된 원소 = " + priorityQueueHighest.poll());
    System.out.println("현재 최대 힙 큐의 루트 = " + priorityQueueHighest.peek());
    System.out.println("삭제4, 삭제된 원소 = " + priorityQueueHighest.poll());

    if (priorityQueueHighest.isEmpty()) {
      System.out.println("최대 힙 큐가 비었습니다.");
    } else {
      System.out.println("최대 힙 큐에 아직 " + priorityQueueHighest.size() + "개의 원소가 있습니다.");
    }

  }
}

 

출력 // 5, 4, 3, 2, 1 큰 순서대로 삭제 현재 최대 힙 큐의 루트 = 5 삭제1, 삭제된 원소 = 5 현재 최대 힙 큐의 루트 = 4 삭제2, 삭제된 원소 = 4 현재 최대 힙 큐의 루트 = 3 삭제3, 삭제된 원소 = 3 현재 최대 힙 큐의 루트 = 2 삭제4, 삭제된 원소 = 2 최대 힙 큐에 아직 1개의 원소가 있습니다.