우선 순위 큐 Java

튜토리얼
Java

가끔 우리는 특정한 순서로 대기열의 항목을 처리해야 합니다. 우선순위 큐는 그 일을 수행하는 자료 구조입니다. Java 우선순위 큐는 “일반적인” 대기열과 다릅니다. “선입선출”이 아니라, 항목들을 우선순위 순서대로 검색합니다.

우선순위 큐 Java

java.util.PriorityQueue 클래스는 내부적으로 우선순위 힙 구현을 사용하여 이러한 데이터 유형의 구현을 제공합니다. Java PriorityQueue는 경계가 없는 큐입니다. 이것은 Java 1.5에 소개되었으며 Java SE 8 릴리스에서 개선되었습니다. PriorityQueue는 내부적으로 “우선순위 힙” 데이터 구조를 따라 구현됩니다. 다음은 PriorityQueue 클래스 계층 구조입니다: PriorityQueue 클래스 다이어그램:

Java PriorityQueue 생성자

  1. PriorityQueue() – 기본 초기 용량인 11로 PriorityQueue를 생성합니다.
  2. PriorityQueue(Collection c) – 지정된 컬렉션의 요소로 PriorityQueue를 생성합니다.
  3. PriorityQueue(int initialCapacity) – 지정된 초기 용량으로 우선 순위 큐를 생성합니다.
  4. PriorityQueue(int initialCapacity, Comparator comparator) – 제공된 초기 용량으로 우선 순위 큐를 생성하며, 요소의 순서는 지정된 비교기에 따라 정렬됩니다.
  5. PriorityQueue(PriorityQueue c) – 지정된 우선 순위 큐의 요소를 포함하는 우선 순위 큐를 생성합니다.
  6. PriorityQueue(SortedSet c) – 지정된 정렬된 세트의 요소를 포함하는 우선 순위 큐를 생성합니다.

우선 순위 큐 요소는 우리가 만들 때 Comparator를 제공하지 않는 한 자연적인 순서에 따라 정렬됩니다. 요소는 기본적으로 오름차순으로 정렬되며, 따라서 큐의 헤드는 우선 순위가 가장 낮은 요소입니다. 동시에 헤드가 될 수 있는 두 요소가 있는 경우, 이러한 결합은 임의로 해결됩니다.

Java 우선 순위 큐 예제

다양한 작업을 포함하는 PriorityQueue를 만들어 봅시다:

PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

이렇게 하면 String의 자연적인 순서대로 작업이 정렬된 우선 순위 큐가 생성됩니다. 자연적인 순서의 역순으로 작업을 정렬하는 다른 PriorityQueue를 만들어 봅시다. 따라서 비교기를 전달해야 합니다:

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

Java PriorityQueue 메서드

이제 PriorityQueue에서 사용 가능한 모든 메서드를 살펴보고 사용해 봅시다:

  1. Boolean add(E e) – 이 메서드는 지정된 요소를 큐에 삽입합니다. 이미 이 메서드를 사용하여 큐에 5개의 작업을 추가했습니다.

  2. Comparator comparator() – 이 메서드는 이 큐의 요소를 정렬하는 데 사용된 Comparator를 반환합니다. Comparator가 지정되지 않았고 큐가 요소의 자연 순서에 따라 정렬된 경우 null을 반환합니다. 따라서 다음을 수행하면:

    System.out.println(tasks.comparator());
System.out.println(reverseTasks.comparator());

    출력은 다음과 같습니다:

    null
java.util.Collections$ReverseComparator@15db9742

  3. boolean contains(Object o) – 지정된 요소가 큐에 포함되어 있는 경우 true를 반환합니다. “task3″이 Priority 큐 tasks에 속하는지 확인해 봅시다:

    System.out.println(tasks.contains("task3"));

    이렇게 출력됩니다:

    true

  4. boolean offer(E e) – add() 메소드와 마찬가지로 이 메소드는 큐에 요소를 추가합니다. offer() 및 add() 메소드는 용량 제한이 있는 큐의 경우 실제로 약간 다르지만 PriorityQueue의 경우 둘 다 동일합니다. add()와 달리, offer()은 요소를 큐에 추가하지 못해도 예외를 던지지 않습니다.

  5. E peek() – 이 큐의 헤드를 검색하거나 이 큐가 비어있는 경우 null을 반환합니다. 다시 말해, 이는 최고 우선순위의 요소를 반환합니다. 따라서 다음 코드:

    System.out.println(tasks.peek());
System.out.println(reverseTasks.peek());

    다음을 얻습니다:

    task1
task5

  6. 이 poll() – 이 메서드는 큐의 맨 앞에서(가장 높은 우선순위의 요소)를 가져오거나 큐가 비어있으면 null을 반환합니다. 그러나 peek()과 달리 요소를 제거합니다. 따라서 poll()을 호출하면 다음과 같습니다:

    System.out.println("작업에서 폴: " + tasks.poll());
System.out.println("reverseTasks에서 폴: " + reverseTasks.poll());

    그런 다음 peek:

    System.out.println("작업에서 픽: " + tasks.peek());
System.out.println("reverseTasks에서 픽: " + reverseTasks.peek());

    다음 출력이 생성됩니다:

    작업에서 폴: 작업1
reverseTasks에서 폴: 작업5
작업에서 픽: 작업2
reverseTasks에서 픽: 작업4

  7. int size() – 큐의 요소 수를 반환합니다.

  8. boolean remove(Object o) – 지정된 요소를 큐에서 제거합니다(요소가 있는 경우). 두 개의 동일한 요소가 있는 경우 하나만 제거합니다.

  9. Object[] toArray() – 큐의 모든 요소를 포함하는 배열을 반환합니다.

  10. T[] toArray(T[] a) – 모든 요소가 포함된 배열을 반환하며, 반환된 배열의 유형은 지정된 배열의 유형과 동일합니다.

  11. Iterator iterator() – 큐에 대한 반복자를 반환합니다.

  12. void clear() – 큐에서 모든 요소를 제거합니다.

이 외에도 PriorityQueue는 Collection 및 Object 클래스에서 메서드를 상속합니다.

Java PriorityQueue 시간 복잡도

  1. 인큐 및 디큐 메서드의 시간 복잡도는 O(log(n))입니다.
  2. remove(Object) 및 contains(Object) 메서드의 시간 복잡도는 선형입니다.
  3. 검색 메서드의 경우 상수 시간 복잡도를 가지고 있습니다.

이 우선 순위 큐의 구현은 스레드 안전하지 않습니다. 따라서 동기화된 액세스가 필요한 경우 PriorityBlockingQueue를 사용해야 합니다. 참조: API 문서

Source:
https://www.digitalocean.com/community/tutorials/priority-queue-java