Java 우선순위 대기열: 기존 대기열이 아님

이 기사에서는 Queue 인터페이스를 구현하는 우선 순위 큐인 Java 클래스를 배웁니다. 프로그래머는 일반 대기열 인터페이스에 대해 무엇을 알고 있습니까? 우선, 이 인터페이스는 FIFO 원칙 또는 "선입 선출"을 기반으로 합니다. 이는 일반적인 의미에서 일반 대기열을 상기시킵니다. McDrive에서 커피를 받고 싶습니까? 당신의 차가 창가 근처에 첫 번째라면, 당신은 다음 운전자보다 먼저 커피를 받을 것입니다.

대기열 인터페이스 선언

public interface Queue<E> extends Collection<E>

우선순위 큐란?

우선순위 대기열이란 무엇입니까? 먼저 뒤에서 요소를 삽입하고 머리에서 요소를 제거하는 경우 Queue 인터페이스를 구현하는 클래스입니다. 그러나 그것은 내부의 일반적인 대기열이 아닙니다. Java 우선 순위 큐 요소의 순서는 요소의 우선 순위에 따라 다릅니다. 우선 순위가 가장 높은 요소가 대기열의 맨 위로 이동됩니다. 순위가 가장 높은 요소를 삭제(서빙)하면 두 번째 요소가 커피를 받으러 헤드로 이동합니다. 우선 순위는 어떻게 결정됩니까? 문서에 따르면 우선 순위 큐의 요소는 사용된 생성자에 따라 자연 순서에 따라 또는 큐 생성 시 제공되는 비교기에 의해 정렬됩니다. 우선 순위 최소 힙을 기반으로 하는 우선 순위 대기열입니다. 즉, 숫자 대기열 요소의 경우 대기열의 첫 번째 요소는 이러한 숫자의 최소값이 됩니다. 신입생들은 이 정의를 읽은 후 꽤 자주 우선순위 큐가 선형적인 의미에서 정렬된다고 생각하기 시작합니다. 즉, 요소가 자연수 인 대기열을 사용하는 경우 첫 번째 요소가 가장 작고 마지막 요소가 가장 큽니다. 이것은 전적으로 사실이 아닙니다. 우선순위 큐가 실제로 어떻게 작동하고 무엇을 제공하는지 이해하려면 힙이 어떻게 작동하는지 알아야 합니다. 잠시 후 예제를 사용하여 우선순위 큐의 내부 구조를 고려합니다. 이제 외부 속성에 대해 살펴 보겠습니다. 그러면 첫 번째 요소가 가장 작고 마지막 요소가 가장 큽니다. 이것은 전적으로 사실이 아닙니다. 우선순위 큐가 실제로 어떻게 작동하고 무엇을 제공하는지 이해하려면 힙이 어떻게 작동하는지 알아야 합니다. 잠시 후 예제를 사용하여 우선순위 큐의 내부 구조를 고려합니다. 이제 외부 속성에 대해 살펴 보겠습니다. 그러면 첫 번째 요소가 가장 작고 마지막 요소가 가장 큽니다. 이것은 전적으로 사실이 아닙니다. 우선순위 큐가 실제로 어떻게 작동하고 무엇을 제공하는지 이해하려면 힙이 어떻게 작동하는지 알아야 합니다. 잠시 후 예제를 사용하여 우선순위 큐의 내부 구조를 고려합니다. 이제 외부 속성에 대해 살펴 보겠습니다.

PriorityQueue 클래스 생성자 및 선언

PriorityQueue 클래스는 Java에서 우선 순위 대기열을 구성하는 6가지 방법을 제공합니다.

• PriorityQueue() - 자연 순서에 따라 요소를 정렬하는 기본 초기 용량(11)이 있는 빈 큐입니다.
• PriorityQueue(Collection c) - 지정된 컬렉션의 요소를 포함하는 빈 큐입니다.
• PriorityQueue(int initialCapacity) - 자연 순서에 따라 요소를 정렬하는 지정된 초기 용량이 있는 빈 큐입니다.
• PriorityQueue(int initialCapacity, Comparator comparator) - 지정된 비교기에 따라 요소를 정렬하는 지정된 초기 용량이 있는 빈 큐입니다.
• PriorityQueue(PriorityQueue c) - 지정된 우선 순위 큐의 요소를 포함하는 빈 큐입니다.
• PriorityQueue(SortedSet c) - 지정된 정렬 세트의 요소를 포함하는 빈 큐입니다.

Java의 우선 순위 큐는 다음과 같이 선언됩니다.

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

PriorityQueue 생성

정수의 우선 순위 큐를 만들어 봅시다. 우선 순위 대기열 구현, Java 코드:

PriorityQueue<Integer> numbers = new PriorityQueue<>();

인수가 없는 우선 순위 큐를 만들었습니다. 이 경우 우선 순위 큐의 헤드는 큐의 최소 개수입니다. 머리를 제거하면 다음으로 가장 작은 요소가 이 자리를 차지합니다. 따라서 오름차순으로 대기열에서 요소를 제거할 수 있습니다. 필요한 경우 Comparator 인터페이스를 사용하여 주문 원칙을 변경할 수 있습니다.

자바 PriorityQueue 메서드

PriorityQueue Java 클래스에는 요소를 추가, 제거 및 확인하는 중요한 메소드가 있습니다.

우선 순위 대기열에 요소 삽입

• boolean add(object) 지정된 요소를 우선 순위 대기열에 삽입합니다. 성공하면 true를 반환합니다. 대기열이 가득 차면 메서드에서 예외가 발생합니다.
• boolean offer(object)는 지정된 요소를 이 우선 순위 대기열에 삽입합니다. 대기열이 가득 차면 메서드는 false를 반환합니다.

추가 작업을 모두 사용할 수 있으며 대부분의 경우 차이가 없습니다. 다음은 우선 순위 대기열에 요소를 시작하고 추가하는 간단한 예입니다.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

출력은 다음과 같습니다.

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

요소의 순서가 이상한 것 같습니다. 나중에 설명하겠습니다.

우선순위 큐에서 요소 검색 및 제거

• boolean remove(object)는 지정된 요소가 있는 경우 이 대기열에서 단일 인스턴스를 제거합니다.
• 객체 poll()은 이 대기열의 헤드를 검색하고 제거합니다. 대기열이 비어 있으면 null을 반환합니다.
• void clear()는 우선순위 큐에서 모든 요소를 ​​제거합니다.
• Object element()는 이 큐의 헤드를 제거하지 않고 검색합니다. 대기열이 비어 있으면 NoSuchElementException이 발생합니다 .
• Object peek()는 대기열을 제거하지 않고 대기열의 헤드를 검색합니다. 대기열이 비어 있으면 null을 반환합니다.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

출력:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

보시다시피 element() 메서드를 사용하여 빈 Queue의 헤드를 인쇄하려고 하면 NoSuchElementexception 이 발생합니다 .

PriorityQueue 비교기

• Comparator comparator()는 대기열의 요소를 정렬하는 데 사용되는 비교기를 반환합니다. 대기열이 해당 요소의 자연 순서에 따라 정렬된 경우 null을 반환합니다.

Java 우선순위 큐, 비교기가 있는 예

위의 코드 예제에서는 자연(오름차순) 순서를 사용했지만 때때로 이를 변경해야 합니다. 다음은 Comparator 인터페이스를 구현하는 자체 내부 비교기 클래스를 생성하는 Java 우선순위 대기열 예제입니다. 비교기는 가장 큰 것부터 가장 작은 것까지 요소를 정렬합니다.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

출력:

the head of Queue = 5
5
4
3
2
1

Queue의 헤드는 이제 최소 요소가 아닌 최대 요소이며 순서가 역순으로 변경되었습니다.

반복자를 사용하여 PriorityQueue 반복

ProrityQueue는 Collection 프레임워크의 일부이며 Iterable<> 인터페이스를 구현합니다. 우선 순위 큐의 요소를 반복하려면 iterator() 메서드를 사용할 수 있습니다. 다음은 예입니다.

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

출력:

1 2 4 5 3 

더 많은 PriorityQueue 메서드

• 부울 contains(객체 o)는 대기열에 o 요소가 포함된 경우 true를 반환합니다.
• int size()는 이 대기열의 요소 수를 반환합니다.
• Object[] toArray()는 이 대기열의 모든 요소를 ​​포함하는 배열을 반환합니다.

다음은 예입니다.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

출력:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

PriorityQueue 자바 8 정의

priorityqueue java 8 설명서를 열면 다음 정의를 찾을 수 있습니다. 우선 순위 힙을 기반으로 하는 제한 없는 우선 순위 큐입니다. 우선 순위 큐의 요소는 사용되는 생성자에 따라 자연 순서에 따라 또는 큐 생성 시 제공되는 Comparator에 따라 순서가 지정됩니다. 우선 순위 대기열은 null 요소를 허용하지 않습니다. 자연 순서에 의존하는 우선 순위 큐는 비교 불가능한 개체의 삽입도 허용하지 않습니다(그렇게 하면 ClassCastException이 발생할 수 있음). 힙은 여기서 매우 중요한 단어입니다. 우선순위 대기열 요소 순서 지정의 속성을 설명합니다.

PriorityQueue 작업의 원리: Binary Heap

예부터 시작하겠습니다. Queue 인터페이스를 구현하는 두 개의 개체를 만들어 보겠습니다. 그들 중 하나는 LinkedList이고 두 번째는 PriorityQueue입니다. 둘 다 5개의 Integer 요소(1,2,3,4 및 5)를 가지고 있으며 가장 큰 것부터 가장 작은 것까지 요소를 대기열에 넣기 시작합니다. 따라서 첫 번째는 5, 그 다음에는 4, 3, 2가 되고 마지막 것은 1이 됩니다. 그런 다음 두 목록을 모두 인쇄하여 순서를 확인하십시오.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

이러한 코드 작업의 결과는 다음과 같습니다.

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

연결된 목록 순서는 예측 가능하고 이해할 수 있습니다. FIFO 원칙에 따라 주문됩니다. 우리는 5로 시작했으므로 이 요소가 줄의 첫 번째 요소이고 그 다음에는 4가 됩니다. 우선 순위 대기열 순서에 대해 무엇을 알 수 있습니까? Docs는 우선 순위 큐의 요소가 자연 순서에 따라 또는 큐 구성 시간에 제공된 비교기에 의해 정렬된다고 말했습니다. 그러나 이 순서는 선형 정렬 의미에서 "자연스러운" 것으로 보이지 않습니다. [1, 2, 4, 5, 3]이 아니라 [1, 2, 3, 4, 5]를 기대합니다. 검색 순서가 왜 그런지 이해하려면 힙을 기반으로 하는 우선 순위 큐를 기억해야 합니다. 힙은 무엇입니까? 이진 트리 기반의 데이터 구조입니다.. 힙의 주요 속성: 각 부모의 우선 순위가 자식의 우선 순위보다 큽니다. 각 부모가 2명 이하의 자식을 갖고 레벨 채우기가 위에서 아래로(동일한 레벨에서 왼쪽에서 오른쪽으로) 진행되는 경우 트리를 완전한 이진법이라고 합니다. 이진 힙은 요소가 추가되거나 제거될 때마다 자체적으로 재구성됩니다. 최소 힙의 경우 삽입 순서에 관계없이 가장 작은 요소가 루트로 이동합니다. 이 최소 힙을 기반으로 하는 우선 순위 큐입니다. 즉, 숫자 대기열 요소의 경우 대기열의 첫 번째 요소는 이러한 숫자의 최소값이 됩니다. 루트를 삭제하면 그 다음으로 작은 것이 루트가 됩니다.

우리의 예를 들어 봅시다.

1단계. 우선 순위 대기열에 '5'를 넣습니다. 뿌리가 됩니다. 2단계. 우선 순위 대기열에 '4'를 추가합니다. 4 <5이므로 새 요소는 이전 요소보다 높아야 합니다. 4는 루트가 되고 5는 왼쪽 자식입니다. 이제 Java의 데이터 구조는 [4, 5]입니다. 3단계. '3'을 추가합니다. 일시적으로 루트(4)의 오른쪽 자식이 됩니다. 그러나 3 < 4이므로 올려야 합니다. 3과 4를 교환합니다. 이제 [3, 5, 4]와 같은 구조가 있습니다. 4단계. '2'를 추가합니다. 5. 2<5의 왼쪽 자식이 되므로 교환한다. 2는 3, 2 < 3의 왼쪽 자식이 되므로 한 번 더 교환 과정을 거칩니다. 이제 [2,3,4,5] 구조가 있습니다 . 5단계.우리는 '1'을 추가합니다. 3의 오른쪽 자식에서 2의 왼쪽 자식으로 오다가 루트로 이동합니다. 결과 데이터 구조: [1,2,4,5,3] 제거 프로세스는 루트에서 시작하여 반대 절차를 유발합니다. 따라서 먼저 루트로 1이 있고 그 다음에는 2, 3, 4 그리고 마지막으로 5가 있습니다. 이것이 poll() 제거 작업을 사용하는 이유입니다.

while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }

선형 센스 출력에서 ​​"정렬"되었습니다.

1
2
3
4
5

따라서 우선 순위 대기열은 일부 작업에 효과적일 수 있습니다. 각 요소를 삽입하고 삭제하는 데 O(log N) 시간이 걸리며 O(1)에서 최소 요소를 얻을 수 있습니다. 전체 예는 다음과 같습니다.

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

우선 순위 대기열은 이진 힙을 기반으로 하므로 요소를 선형 정렬 순서로 유지하지 않는다는 점을 이해하는 것이 중요합니다. 루트에서 리프까지의 모든 방법은 순서가 있지만 루트에서 다른 방법은 그렇지 않습니다. 즉, 대기열의 최소 요소를 매우 빠르게 얻을 수 있습니다.

우선 순위 큐에 대해 알아야 할 사항. 간략한 목록

• 우선순위 큐는 NULL 객체를 허용하지 않습니다.
• PriorityQueue에는 비교 대상만 추가할 수 있습니다.
• 우선 순위 큐는 일종의 이진 트리인 최소 힙으로 구성됩니다. 최소 요소는 루트입니다. 우선 순위 대기열의 객체는 기본적으로 자연 순서로 정렬됩니다.
• 맞춤 주문이 필요한 경우 Comparator를 사용할 수 있습니다.
• PriorityQueue는 스레드로부터 안전하지 않으므로 PriorityBlockingQueue를 사용하여 동시 환경에서 작업하는 것이 좋습니다.
• PriorityQueue는 추가 및 폴링 방법에 O(log(n)) 시간을 제공하고 최소한의 요소를 얻기 위해 O(1)을 제공합니다.