Java Priority Queue: не е класическа опашка

В тази статия научаваме приоритетна опашка, Java клас, който имплементира Queue интерфейс. Какво знае един програмист за обикновения интерфейс на опашката? На първо място, този интерфейс е базиран на принципа FIFO or „първи влязъл, първи излязъл“. Това напомня на обикновена опашка в общото й meaning. Искате ли да получите кафе от McDrive? Ако колата ви е първа до прозореца, ще получите кафето си преди шофьора, който е следващият.

Декларация на интерфейса на опашката

public interface Queue<E> extends Collection<E>

Какво е приоритетна опашка

Какво е приоритетна опашка? На първо място, това е клас, който имплементира интерфейса Queue в случай на вмъкване на елемент отзад и премахване на елемент от главата. Вътре обаче не е обикновена опашка. Редът на елементите на приоритетната опашка на Java зависи от приоритета на елементите. Елементът с най-висок приоритет ще бъде преместен в началото на опашката. Ако изтриете (сервирате) най-високо класирания елемент, вторият отива при главата, за да си вземе кафето. Как се определя приоритетът? Съгласно documentацията, елементите на приоритетната опашка се подреждат според естествения им ред or чрез Comparator, предоставен по време на изграждане на опашка, в зависимост от това кой конструктор се използва. Опашка с приоритет, базирана на минимална купчина с приоритет. Това означава, че в случай на елементи от опашката с числа, първият елемент на опашката ще бъде минималното от тези числа. Доста често, след като прочетат тази дефиниция, новобранците започват да мислят, че опашката с приоритети е сортирана в линеен смисъл. Тоест, ако, да речем, използваме опашка, чиито елементи са естествени числа, тогава първият елемент ще бъде най-малкият, а последният - най-големият. Това не е съвсем вярно. За да разберете How всъщност работи приоритетната опашка и Howво дава, трябва да разберете How работи купчината. Разглеждаме вътрешната структура на приоритетната опашка, като използваме пример малко по-късно. Сега нека се спрем на неговите външни атрибути. тогава първият елемент ще бъде най-малкият, а последният - най-големият. Това не е съвсем вярно. За да разберете How всъщност работи приоритетната опашка и Howво дава, трябва да разберете How работи купчината. Разглеждаме вътрешната структура на приоритетната опашка, като използваме пример малко по-късно. Сега нека се спрем на неговите външни атрибути. тогава първият елемент ще бъде най-малкият, а последният - най-големият. Това не е съвсем вярно. За да разберете How всъщност работи приоритетната опашка и Howво дава, трябва да разберете How работи купчината. Разглеждаме вътрешната структура на приоритетната опашка, като използваме пример малко по-късно. Сега нека се спрем на неговите външни атрибути.

Конструктори и декларация на клас PriorityQueue

Класът PriorityQueue предоставя 6 различни начина за конструиране на приоритетна опашка в Java.

• 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 code:

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

Създадохме приоритетна опашка без аргументи. В този случай главата на приоритетната опашка е минималният номер на опашката. Ако премахнете главата, следващият най-малък елемент ще заеме това място. Така че можете да премахвате елементи от опашката във възходящ ред. Ако е необходимо, можете да промените принципа на подреждане чрез интерфейса на Comparator.

Методи на Java 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) премахва едно копие на посочения елемент от тази опашка, ако е налице.
• 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() води до NoSuchElementexception .

Сравнител на PriorityQueue

• Comparator comparator() връща компаратора, използван за подреждане на елементите в опашката. Връща null, ако опашката е сортирана според естествения ред на нейните елементи.

Java приоритетна опашка, пример с компаратор

Използвахме естествен (възходящ) ред в примерите за code по-горе, но понякога трябва да го променим. Ето пример за приоритетна опашка на 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

Главата на опашката вече не е минималният, а максималният елемент и редът е променен на обратен.

Итерация над PriorityQueue с помощта на итератор

ProrityQueue е част от рамката на колекцията и имплементира интерфейса 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

• boolean contains(Object o) връща true, ако опашката съдържа o елемента.
• 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 Java 8

Ако отворите documentацията на priorityqueue java 8, ще намерите там следващата дефиниция: неограничена приоритетна опашка, базирана на приоритетна купчина. Елементите на приоритетната опашка се подреждат според естествения им ред or чрез компаратор, предоставен по време на изграждане на опашка, в зависимост от това кой конструктор се използва. Приоритетната опашка не позволява нулеви елементи. Приоритетна опашка, разчитаща на естествено подреждане, също не позволява вмъкване на несравними обекти (това може да доведе до 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)

Резултатът от работата на този code е следният:

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

Е, редът на свързания списък е предвидим и разбираем. Подреден е на принципа FIFO. Започнахме с 5, така че този елемент е първият в редицата, след това отива 4 и така нататък. Какво можем да кажем за приоритетния ред на опашката? Документите казаха, че елементите на приоритетната опашка се подреждат според естествения им ред or чрез Comparator, предоставен по време на изграждане на опашката. Този ред обаче не изглежда „естествен“ в смисъл на линейно сортиране. По-скоро бихме очаквали [1, 2, 3, 4, 5], а не [1, 2, 4, 5, 3]. За да разберем защо редът на извличане е такъв, трябва да си припомним тази приоритетна опашка, базирана на купчина. Какво е купчината? Това е структура от данни, базирана на двоично дърво. Основното свойство на купчината: приоритетът на всеки родител е по-голям от приоритетите на неговите деца. Позволете ми да ви напомня, че едно дърво се нарича пълно двоично, ако всеки родител има не повече от две деца и запълването на нивата върви отгоре надолу (от едно и също ниво - отляво надясно). Двоичната купчина се реорганизира всеки път, когато се добавят or премахват елементи от нея. В случай на min-heap, най-малкият елемент отива в корена, независимо от реда на неговото вмъкване. Приоритетна опашка на базата на този min-heap. Това означава, че в случай на елементи от опашката с числа, първият елемент на опашката ще бъде минималният от тези числа. Ако изтриете корена, следващият най-малък става корен.

Нека се обърнем към нашия пример.

Стъпка 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] Процесът на премахване започва от корен и провокира обратните proceduresи. И така, първо имаме 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.
• Приоритетната опашка е изградена като min heap, вид двоично дърво. Минималният елемент е корен. Обектите на приоритетната опашка са подредени по подразбиране в естествен ред.
• Можете да използвате Comparator, ако имате нужда от персонализирана поръчка.
• PriorityQueue не е безопасен за нишки, така че по-добре използвайте PriorityBlockingQueue за работа в едновременна среда.
• PriorityQueue осигурява O(log(n)) време за методи за добавяне и анкета и O(1) за получаване на минимални елементи.