Очередь приоритета представляет собой несколько аналогичную структуру данных в очереди . Разница заключается в том, как элементы обрабатываются:
- Стандартная очередь строго следует принципу FIFO (первым пришел-последним вышел).
- Очередь с приоритетом не соответствует принципу FIFO.
В очереди с приоритетами элементы удаляются из очереди в зависимости от их приоритета. Это означает, что:
Каждый элемент в очереди приоритетов должен иметь связанный с ним приоритет.
Как вы уже догадались, элемент с наивысшим приоритетом удаляется из очереди (исключается из очереди).
Но как определить приоритет элементов в очереди?
Определение приоритетов для элементов
По сути, у вас есть две альтернативы для определения приоритетов элементов в очереди. Вы также можете
- Элементы заказа основаны на их естественном порядке.
- Заказать элементы с помощью специального компаратора.
В этой статье мы сосредоточимся на том, как реализовать приоритетную очередь. Поэтому для простоты мы упорядочим элементы на основе их естественного порядка .
В нашем примере приоритетная очередь будет ограничена int, поэтому естественное упорядочение вполне подойдет. Однако имейте в виду, что это только для демонстрационных целей.
Если вы хотите реализовать очередь с приоритетами в реальной жизни, вы, вероятно, захотите использовать непатентованные средства — или просто сделайте это, как любой другой разработчик, и используйте встроенный java.util.PriorityQueue.
Чтобы поддерживать реализацию нашего примера в соответствии со спецификацией Java, наименьший элемент определяется как элемент с наивысшим приоритетом.
Операции с приоритетными очередями
Самый базовый набор операций для любой реализации очереди:
-
enqueue— Вставка элемента в очередь. -
dequeue— Удаление элемента из очереди. -
isEmpty— Возвращение true, если очередь пуста. -
size— Возвращение размера / количества элементов в очереди. -
contains— Возвращение true, если очередь содержит данный элемент. -
peek— Возврат переднего элемента очереди, не удаляя его.
Обратите внимание, что реализация Java очереди с приоритетами использует разные имена для методов. В производственной среде я настоятельно рекомендую вам использовать реализацию очереди с приоритетами по умолчанию вместо того, чтобы «выращивать ее».
Реализация очереди приоритетов
Теперь давайте реализуем очередь неуниверсального приоритета в Java. Мы будем реализовывать одну операцию за раз, но сначала нам нужно решить, какую внутреннюю структуру данных мы хотим использовать.
Массив прекрасно, так что мы будем катиться с этим.
Для тех из вас, кто знаком с массивами, вы, вероятно, знаете, что массивы имеют фиксированный размер в Java. Наше решение этой проблемы состоит в том, что мы предоставим приватный метод double(), который «увеличивает» емкость массива.
Скелет кода для приоритетной очереди представлен ниже.
package priorityqueue;
public class PriorityQueue {
private int[] innerArray;
private int size;
public PriorityQueue() {
this.innerArray = new int[10];
size = 0;
}
public void enqueue(int x) {
}
public int dequeue() {
return 0;
}
public int peek() {
return 0;
}
public boolean contains(int x) {
return false;
}
public boolean isEmpty() {
return false;
}
public int size() {
return 0;
}
private void doubleArray() {
}
}
Как видите, мы используем intмассив в качестве внутренней структуры данных и инициализируем его размер по умолчанию в конструкторе до 10. Мы также предоставляем приватную переменную size для отслеживания количества элементов.
Реализация Size, isEmpty и Peek
Реализация sizeи isEmptyметодов так же легко , как он получает. Следует помнить одну вещь: sizeпеременная используется, чтобы избежать цикла по массиву и считать «действительные» целые числа. В конструкторе всем индексам присвоено значение intсо значением 0.
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
Как насчет peek? На самом деле это тоже довольно просто: если размер больше 0, мы возвращаем первый элемент. Если оно меньше нуля, мы бросаем . NoSuchElementException
public int peek() {
if (isEmpty())
throw new NoSuchElementException("The queue is empty");
return innerArray[0];
}
Реализация содержит
Пришло время для реализации , которая должна возвращать true, если очередь содержит предоставленный параметр. contains
Как мы должны это реализовать? Одним наивным способом было бы просто пройтись по массиву и вернуть true, если мы встретимся с указанным intв массиве.
Однако это не сработает! Что если пользователь предоставит нам 0? Как упоминалось ранее, массиву изначально присваивается значение intсо значением по умолчанию, которое равно нулю.
Другими словами: мы получим ложный положительный результат.
Решение? Только цикл по индексам, которые мы знаем, содержит вставленные значения.
public boolean contains(int x) {
// Check for empty.
if(isEmpty())
return false;
// Looping through the positions which contains inserted values,
// ignoring trailing default 0 values.
for(int i = 0; i < size; i++) {
// Comparing
if(innerArray[i] == x)
return true;
}
// None found
return false;
}
Реализация постановки и снятия с очереди
Во-первых, давайте подумаем о том, что мы хотим, если мы вставим / поставим в очередь элемент. Обратите внимание, что мы doubleArray пока игнорируем метод. Мы хотим, чтобы вставленные элементы были помещены в очередь в правильном положении в соответствии с их приоритетом.
Эта визуализация enqueue операции говорит нам о том, что нам придется сместить все элементы с более низким приоритетом на одну позицию вверх в массиве.
public void enqueue(int x) {
// If it is empty, insert in front
if (size == 0) {
size++;
innerArray[0] = x;
return;
}
// If full, we'll have to double the array
if (size() == innerArray.length)
doubleArray();
// Looping through
int temp = x;
for (int i = 0; i < size; i++) {
// If priority is higher, ie. values is lower, we shift.
if (x <= innerArray[i]) {
int next;
temp = innerArray[i];
innerArray[i] = x;
// Shifting
while (i < size - 1) {
next = innerArray[i + 1];
innerArray[i + 1] = temp;
temp = next;
i++;
}
break;
}
}
// Placing, increasing size.
innerArray[size] = temp;
size++;
}
Dequeueработает очень похожим образом.
public int dequeue() {
// NoSuchElement
if (isEmpty())
throw new NoSuchElementException("The queue is empty");
// Storing first int for return
int retValue = innerArray[0];
// Shifting all values downwards
for (int i = 1; i < size; i++) {
innerArray[i - 1] = innerArray[i];
}
innerArray[size - 1] = 0;
size--;
return retValue;
}
Реализация doubleArray
Теперь осталось только реализовать метод, который удваивает массив, если мы превышаем исходный размер. Мы просто копируем содержимое массива в новый массив, который в два раза больше.
private void doubleArray() {
int[] newArr = new int[innerArray.length * 2];
for(int i = 0; i < innerArray.length; i++) {
newArr[i] = innerArray[i];
}
innerArray = newArr;
}
Полная реализация
Полная реализация может быть найдена ниже. Удачного кодирования!
package priorityqueue;
import java.util.NoSuchElementException;
public class PriorityQueue {
private int[] innerArray;
private int size;
public PriorityQueue() {
this.innerArray = new int[10];
size = 0;
}
public void enqueue(int x) {
// If it is empty, insert in front
if (size == 0) {
size++;
innerArray[0] = x;
return;
}
// If full, we'll have to double the array
if (size() == innerArray.length)
doubleArray();
// Looping through
int temp = x;
for (int i = 0; i < size; i++) {
// If priority is higher, ie. values is lower, we shift.
if (x <= innerArray[i]) {
int next;
temp = innerArray[i];
innerArray[i] = x;
// Shifting
while (i < size - 1) {
next = innerArray[i + 1];
innerArray[i + 1] = temp;
temp = next;
i++;
}
break;
}
}
// Placing, increasing size.
innerArray[size] = temp;
size++;
}
public int dequeue() {
// NoSuchElement
if (isEmpty())
throw new NoSuchElementException("The queue is empty");
// Storing first int for return
int retValue = innerArray[0];
// Shifting all values downwards
for (int i = 1; i < size; i++) {
innerArray[i - 1] = innerArray[i];
}
innerArray[size - 1] = 0;
size--;
return retValue;
}
public int peek() {
if (isEmpty())
throw new NoSuchElementException("The queue is empty");
return innerArray[0];
}
public boolean contains(int x) {
// Check for empty.
if (isEmpty())
return false;
// Looping through the positions which contains inserted values,
// ignoring trailing default 0 values.
for (int i = 0; i < size; i++) {
// Comparing
if (innerArray[i] == x)
return true;
}
// None found
return false;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
private void doubleArray() {
int[] newArr = new int[innerArray.length * 2];
for(int i = 0; i < innerArray.length; i++) {
newArr[i] = innerArray[i];
}
innerArray = newArr;
}
}