java priority queue tutorial implementation examples
Този урок обяснява приоритетната опашка на Java и свързаните с нея концепции като сравнителна, минимална и максимална приоритетна опашка заедно с нейното внедряване с примери:
Структурата на данните за приоритетната опашка е специална опашка, в която елементите присъстват не по реда на FIFO, а според естествените елементи или всеки персонализиран сравнител, използван по време на създаването на опашката.
=> Погледнете тук ръководството за начинаещи Java.
Какво ще научите:
Приоритетна опашка в Java
В приоритетната опашка предната част на опашката има най-малко елементи според естественото подреждане, а задната част е насочена към най-големия елемент в опашката.
По-долу е показан пример за приоритетна опашка, състояща се от числа.
java програмиране въпроси и отговори за писмен тест
По този начин, когато елемент бъде премахнат от приоритетната опашка, показана по-горе, тогава той ще бъде най-малкият елемент.
По същия начин, за азбучна приоритетна опашка, ще се вземат предвид ASCII стойностите и елементите на опашката ще бъдат подредени според ASCII стойностите.
По-долу са изброени някои от основните характеристики на PriorityQueue:
- PriorityQueue е несвързана опашка.
- PriorityQueue не позволява нулеви стойности.
- За несравними обекти не можем да създадем приоритетна опашка.
- PriorityQueue наследява от класовете като AbstractQueue, AbstractCollection, Collection и Object.
- Главата или предната част на опашката съдържа най-малкия елемент според естественото подреждане.
- Прилагането на приоритетната опашка не е безопасно за нишки. По този начин, ако желаем синхронизиран достъп, трябва да използваме PriorityBlockingQueue.
Класът PriorityQueue наследява Java Queue Interface и е част от пакета java.util.
Общата декларация за класа PriorityQueue е дадена по-долу:
public class PriorityQueue extends AbstractQueue implements SerializableДиаграмата по-долу показва йерархията на класа за класа PriorityQueue.
Сложност във времето на приоритетната опашка
- Сложността във времето на приоритетната опашка за методите за вмъкване (опашка) и изтриване (отлагане) е O (log (n)).
- Приоритетната опашка има линейна времева сложност за премахване, както и съдържа методи.
- Методите, които извличат елементи от приоритетната опашка, имат постоянна сложност във времето.
Пример за приоритетна опашка в Java
Програмата по-долу демонстрира проста PriorityQueue в Java. Създаваме обект от клас PriorityQueue, добавяме стойности към него и след това показваме съдържанието на Queue с помощта на Iterator.
import java.util.*; class Main{ public static void main(String args()){ PriorityQueue cities_queue=new PriorityQueue(); //initialize the PriorityQueue with values cities_queue.add('Sydney'); cities_queue.add('Venice'); cities_queue.add('New York'); cities_queue.add('California'); cities_queue.add('Melbourne'); //print the head of the PriorityQueue System.out.println('PriorityQueue Head:'+cities_queue.element()); //Define the iterator for PriorityQueue and print its elements System.out.println('
PriorityQueue contents:'); Iterator iter=cities_queue.iterator(); while(iter.hasNext()){ System.out.print(iter.next() + ' '); } } } Изход:
Методи на API за приоритетна опашка на Java
Конструктори:
| Прототип на конструктора | Описание | |
|---|---|---|
| надникнете | E peek() | Връща главата на опашката, без да изтрива елемента. |
| PriorityQueue () | Конструктор по подразбиране, който създава обект PriorityQueue с първоначален капацитет като 1. | |
| PriorityQueue (Колекция c) | Създава обект PriorityQueue с начални елементи от дадена колекция c. | |
| PriorityQueue (int InitialCapacity) | Създава обект PriorityQueue с дадената ‘InitiCapacity’. Елементите са подредени според естествената поръчка. | |
| PriorityQueue (int initialCapacity, компаратор за сравнение) | Създава обект PriorityQueue с дадената ‘InitiCapacity’. Елементите са подредени според дадения компаратор. | |
| PriorityQueue (PriorityQueue c) | Създава обект PriorityQueue от друг обект PriorityQueue, даден от c. | |
| PriorityQueue (SortedSet c) | Създава обект PriorityQueue от SortedSet, даден от c. |
Методи
| Метод | Прототип на метода | Описание |
|---|---|---|
| добавете | булево добавяне (E e) | Добавя елемент e към PriorityQueue. |
| ясно | празно ясно () | Изчиства PriorityQueue, като изтрива всички елементи. |
| компаратор | Comparatorcomparator () | Връща персонализиран сравнител, използван за подреждането на елементи в опашката. |
| съдържа | boolean съдържа (Обект o) | Проверява дали PriorityQueue съдържа дадения елемент o. Връща вярно, ако да. |
| итератор | Итератортератор () | Метод за получаване на итератор за дадената PriorityQueue. |
| оферта | булево предложение (E e) | Вмъкнете даден елемент e в PriorityQueue. |
| анкета | E poll() | Премахва и връща главата на опашката. Връща null, ако опашката е празна. |
| Премахване | булево премахване (обект o) | Премахва екземпляр на даден елемент o, ако той присъства в опашката. |
| размер | размер int () | Връща размера или броя на елементите в тази PriorityQueue. |
| toArray | Обект () към масив () | Връща представяне на масив на дадената PriorityQueue. |
| toArray | T () до масив (T () a) | Връща представяне на масив за дадената приоритетна опашка със същия тип на изпълнение като посочения масив a. |
Внедряване в Java
Нека да демонстрираме горните методи на PriorityQueue с помощта на програма Java.
import java.util.*; class Main { public static void main(String args()) { // Creating empty priority queue PriorityQueue numQueue = new PriorityQueue(); // add elements to numQueue using add() numQueue.add('Five'); numQueue.add('One'); numQueue.add('Seven'); numQueue.add('Three'); numQueue.add('Eleven'); numQueue.add('Nine'); // Print the head element using Peek () method System.out.println('Head element using peek method:' + numQueue.peek()); // Printing all elements System.out.println('
The PriorityQueue elements:'); Iterator iter1 = numQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); // remove head with poll () numQueue.poll(); System.out.println('
After removing an element' + 'with poll function:'); Iterator iter2 = numQueue.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); // Remove 'Three' using remove () numQueue.remove('Three'); System.out.println('
Element 'Three' with' + ' remove function:'); Iterator iter3 = numQueue.iterator(); while (iter3.hasNext()) System.out.print(iter3.next() + ' '); // Check if an element is present in PriorityQueue using contains() boolean ret_val = numQueue.contains('Five'); System.out.println('
Priority queue contains 'Five' ' + 'or not?: ' + ret_val); // get array equivalent of PriorityQueue with toArray () Object() numArr = numQueue.toArray(); System.out.println('
Array Contents: '); for (int i = 0; i Изход:
какво е интеграционно тестване с пример
Приоритетна опашка в Java 8
Java 8 добавя още един метод към клас PriorityQueue, т.е. ‘spliterator ()’.
Подробностите за този метод са дадени по-долу.
Име на метода: сплитер
Прототип на метода: публичен окончателен Spliterator spliterator ()
Описание на метода: Този метод създава сплайтер над елементите PriorityQueue. Този сплитератор е късно свързващ и бърз.
Сравнител на приоритетни опашки
Както вече споменахме, приоритетните елементи са естествено подредени. Ако искаме да променим подреждането, трябва да посочим компаратор и да го използваме по време на създаването на обекта PriorityQueue. След това PriorityQueue използва този компаратор, за да подреди елементите му.
Долната програма Java демонстрира използването на персонализиран сравнител за подреждане на елементи. В тази програма ние дефинираме нов персонализиран сравнител, в който заместваме метода „сравнение“. Методът за сравнение се използва за подреждане на елементите на PriorityQueue според дължината.
import java.util.*; public class Main { public static void main(String() args) { // A custom comparator that compares two Strings by their length. Comparator customComparator = new Comparator() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } }; // Create a Priority Queue with a custom Comparator PriorityQueue colorsPriorityQueue = new PriorityQueue(customComparator); // Add items to a Priority Queue colorsPriorityQueue.add('Red'); colorsPriorityQueue.add('Green'); colorsPriorityQueue.add('Blue'); colorsPriorityQueue.add('Cyan'); colorsPriorityQueue.add('Magenta'); colorsPriorityQueue.add('Yellow'); // Printing all elements System.out.println('
The PriorityQueue elements with custom Comparator:'); Iterator iter1 = colorsPriorityQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); } } Изход:
Минимална опашка за приоритет в Java
Естественото подреждане на приоритетната опашка има най-малкия или най-малкия елемент в началото на опашката и по този начин подреждането е възходящо. Това се нарича „Минимална опашка с приоритет“ с възходящ ред на елементите.
Програмата за Java по-долу показва изпълнението на Min Priority Queue в Java.
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with default ordering PriorityQueue pq = new PriorityQueue(); //add element to the PriorityQueue pq.add(8); pq.add(6); pq.add(4); pq.add(2); pq.add(12); pq.add(10); //display the min PriorityQueue System.out.println('The min Priority Queue (natural ordering) contents:'); Integer val = null; while( (val = pq.poll()) != null) { System.out.print(val + ' '); } } } Изход:
Max Priority Queue в Java
Докато опашката с минимален приоритет има елементи във възходящ ред, опашката с максимален приоритет има елементите в низходящ ред, т.е.главата на опашката с максимален приоритет ще върне най-големия елемент в опашката.
Програмата за Java по-долу демонстрира Max Priority Queue в Java.
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with custom comparator to generate max PQ PriorityQueue pq = new PriorityQueue(new Comparator() { public int compare(Integer lhs, Integer rhs) { if (lhs Изход:
Както е показано в горната програма, за да променим естественото подреждане на елементи в опашката с приоритет, трябва да дефинираме персонализиран сравнител.
често задавани въпроси
В # 1) Каква е опашката за приоритет в Java?
Отговор: Специална опашка, в която всички елементи на опашката са подредени според естественото подреждане или с помощта на персонализиран сравнител, се нарича приоритетна опашка. Не спазва заповедта на FIFO.
В # 2) Как да зададете опашка за максимален приоритет в Java?
Отговор: Можем да зададем Max Priority Queue в Java с помощта на персонализиран компаратор, така че главата на опашката да връща най-големия елемент в опашката.
В # 3) Разрешава ли приоритетната опашка дубликати на Java?
Отговор: Да. Приоритетна опашка позволява дублирани стойности.
В # 4) Максимална или минимална опашка за приоритет на Java е максимум или мин?
Отговор: По подразбиране приоритетната опашка в Java е мин. Приоритетна опашка с естествено подреждане. За да го направим максимално, трябва да използваме персонализиран компаратор, така че главата на опашката да връща най-големия елемент в опашката.
В # 5) Сортира ли се приоритетна опашка?
как да отворя торент файл
Отговор: По подразбиране главата на опашката е сортирана и приоритетната опашка има най-малкото елемент като глава. Останалите елементи се подреждат при необходимост.
Заключение
Това завършва урока за приоритетни опашки в Java. Priority Queue реализира интерфейс на опашката и е специална опашка, при която елементите се подреждат според естественото подреждане. Не спазва заповедта на FIFO. За да променим естественото подреждане на опашката с приоритет, можем да използваме персонализирания сравнител.
Приоритетните опашки се използват главно за планиране на принтер, планиране на задачи на процесора и др. Купчината (минимална или максимална) също се реализира с помощта на приоритетни опашки.
=> Прочетете серията Easy Training Training.
Препоръчително четене
- Структура на данните за приоритетна опашка в C ++ с илюстрация
- Приоритетна опашка в STL
- Java Queue - Методи за опашка, внедряване на опашка с примери
- Структура на данните за циркулярна опашка C ++: Внедряване и приложения
- Двойно завършена опашка (Deque) в C ++ с примери
- Структура на данните за опашката в C ++ с илюстрация
- Стекове и опашки в STL
- Урок за JAVA за начинаещи: 100+ практически ръководства за Java видео
