PriorityBlockingQueue, особенности и внутреннее устройство
PriorityBlockingQueue — это реализация интерфейса BlockingQueue в Java, который поддерживает элементы с приоритетом. Очередь использует естественный порядок элементов или компаратор для их упорядочивания. В отличие от обычной очереди, в которой элементы обрабатываются в порядке их вставки, PriorityBlockingQueue позволяет извлекать элементы в соответствии с их приоритетами.
Особенности PriorityBlockingQueue
Приоритетный порядок:
Элементы в очереди сортируются по их естественному порядку или по заданному компаратору.
Высокоприоритетные элементы будут извлекаться первыми.
Неблокирующие операции вставки:
Методы put и offer не блокируются, так как очередь не имеет ограничений на размер.
Блокирующие операции извлечения:
Методы take и poll блокируются, если очередь пуста, до тех пор, пока элемент не станет доступным.
Многопоточность:
PriorityBlockingQueue является потокобезопасной и поддерживает конкурентный доступ из множества потоков.
Без ограничения размера:
Очередь динамически расширяется по мере необходимости и не имеет фиксированного размера.
Внутреннее устройство PriorityBlockingQueue
Базовая структура данных:
Основой PriorityBlockingQueue является массив, который представляет собой бинарную кучу (минимальную кучу).
Бинарная куча — это полное бинарное дерево, где каждый узел меньше или равен своим потомкам (для минимальной кучи).
Синхронизация:
Очередь использует методы синхронизации для обеспечения потокобезопасности.
Основные операции, такие как вставка и удаление элементов, синхронизированы для предотвращения гонок.
Алгоритмы вставки и извлечения:
При вставке нового элемента, он добавляется в конец массива, а затем "плавает вверх" по дереву, чтобы найти свое правильное место.
При извлечении элемента, корневой элемент (с минимальным значением) удаляется, и последний элемент массива перемещается на его место, затем "тонет" вниз, чтобы восстановить свойства кучи.
Пример кода внутреннего устройства
Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://for-each.dev/lessons/b/-java-priority-blocking-queue
https://www.baeldung.com/java-priority-blocking-queue
#Java #Training #Medium #PriorityBlockingQueue
PriorityBlockingQueue — это реализация интерфейса BlockingQueue в Java, который поддерживает элементы с приоритетом. Очередь использует естественный порядок элементов или компаратор для их упорядочивания. В отличие от обычной очереди, в которой элементы обрабатываются в порядке их вставки, PriorityBlockingQueue позволяет извлекать элементы в соответствии с их приоритетами.
Особенности PriorityBlockingQueue
Приоритетный порядок:
Элементы в очереди сортируются по их естественному порядку или по заданному компаратору.
Высокоприоритетные элементы будут извлекаться первыми.
Неблокирующие операции вставки:
Методы put и offer не блокируются, так как очередь не имеет ограничений на размер.
Блокирующие операции извлечения:
Методы take и poll блокируются, если очередь пуста, до тех пор, пока элемент не станет доступным.
Многопоточность:
PriorityBlockingQueue является потокобезопасной и поддерживает конкурентный доступ из множества потоков.
Без ограничения размера:
Очередь динамически расширяется по мере необходимости и не имеет фиксированного размера.
Внутреннее устройство PriorityBlockingQueue
Базовая структура данных:
Основой PriorityBlockingQueue является массив, который представляет собой бинарную кучу (минимальную кучу).
Бинарная куча — это полное бинарное дерево, где каждый узел меньше или равен своим потомкам (для минимальной кучи).
Синхронизация:
Очередь использует методы синхронизации для обеспечения потокобезопасности.
Основные операции, такие как вставка и удаление элементов, синхронизированы для предотвращения гонок.
Алгоритмы вставки и извлечения:
При вставке нового элемента, он добавляется в конец массива, а затем "плавает вверх" по дереву, чтобы найти свое правильное место.
При извлечении элемента, корневой элемент (с минимальным значением) удаляется, и последний элемент массива перемещается на его место, затем "тонет" вниз, чтобы восстановить свойства кучи.
Пример кода внутреннего устройства
import java.util.concurrent.PriorityBlockingQueue;
public class PriorityBlockingQueueExample {
public static void main(String[] args) throws InterruptedException {
PriorityBlockingQueue<Integer> queue = new PriorityBlockingQueue<>();
// Добавление элементов в очередь
queue.put(10);
queue.put(20);
queue.put(5);
// Извлечение элементов из очереди
System.out.println(queue.take()); // 5
System.out.println(queue.take()); // 10
System.out.println(queue.take()); // 20
}
}
Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://for-each.dev/lessons/b/-java-priority-blocking-queue
https://www.baeldung.com/java-priority-blocking-queue
#Java #Training #Medium #PriorityBlockingQueue
for-each.dev
Руководство по PriorityBlockingQueue в Java | for-each.dev
Введение в Java's PriorityBlockingQueue с примерами использования
Основные методы PriorityBlockingQueue и примеры использования
put(E e):
Вставляет элемент в очередь. Этот метод никогда не блокируется, так как очередь не имеет ограничений на размер.
offer(E e):
Вставляет элемент в очередь. Возвращает true, если элемент был успешно вставлен.
take():
Извлекает и удаляет элемент с наивысшим приоритетом из головы очереди. Блокируется, если очередь пуста.
poll(long timeout, TimeUnit unit):
Пытается извлечь элемент из головы очереди, блокируясь в течение указанного времени ожидания. Возвращает элемент или null, если тайм-аут истек.
peek():
Возвращает элемент с наивысшим приоритетом, но не удаляет его из очереди. Возвращает null, если очередь пуста.
size():
Возвращает количество элементов в очереди.
contains(Object o):
Проверяет, содержится ли указанный элемент в очереди.
remove(Object o):
Удаляет указанное значение из очереди, если оно присутствует.
Пример использования PriorityBlockingQueue
Обработка задач с приоритетами:
PriorityBlockingQueue можно использовать для реализации планировщика задач, где задачи с высоким приоритетом обрабатываются первыми.
#Java #Training #Medium #PriorityBlockingQueue
put(E e):
Вставляет элемент в очередь. Этот метод никогда не блокируется, так как очередь не имеет ограничений на размер.
PriorityBlockingQueue<Integer> queue = new PriorityBlockingQueue<>();
queue.put(15); // Вставка элемента в очередь
offer(E e):
Вставляет элемент в очередь. Возвращает true, если элемент был успешно вставлен.
boolean success = queue.offer(25); // Вставка элемента, возвращает true
take():
Извлекает и удаляет элемент с наивысшим приоритетом из головы очереди. Блокируется, если очередь пуста.
Integer element = queue.take(); // Блокирующее извлечение элемента
poll(long timeout, TimeUnit unit):
Пытается извлечь элемент из головы очереди, блокируясь в течение указанного времени ожидания. Возвращает элемент или null, если тайм-аут истек.
Integer polledElement = queue.poll(1, TimeUnit.SECONDS); // Пытается извлечь элемент с тайм-аутом
peek():
Возвращает элемент с наивысшим приоритетом, но не удаляет его из очереди. Возвращает null, если очередь пуста.
Integer peekedElement = queue.peek(); // Просмотр элемента без его удаления
size():
Возвращает количество элементов в очереди.
int size = queue.size(); // Получение размера очереди
contains(Object o):
Проверяет, содержится ли указанный элемент в очереди.
boolean contains = queue.contains(15); // Проверка наличия элемента в очереди
remove(Object o):
Удаляет указанное значение из очереди, если оно присутствует.
boolean removed = queue.remove(25); // Удаление элемента из очереди
Пример использования PriorityBlockingQueue
Обработка задач с приоритетами:
PriorityBlockingQueue можно использовать для реализации планировщика задач, где задачи с высоким приоритетом обрабатываются первыми.
import java.util.concurrent.PriorityBlockingQueue;
class Task implements Comparable<Task> {
private int priority;
private String name;
public Task(int priority, String name) {
this.priority = priority;
this.name = name;
}
@Override
public int compareTo(Task other) {
return Integer.compare(this.priority, other.priority);
}
@Override
public String toString() {
return "Task{name='" + name + "', priority=" + priority + '}';
}
}
public class TaskScheduler {
public static void main(String[] args) throws InterruptedException {
PriorityBlockingQueue<Task> taskQueue = new PriorityBlockingQueue<>();
taskQueue.put(new Task(3, "Low priority task"));
taskQueue.put(new Task(1, "High priority task"));
taskQueue.put(new Task(2, "Medium priority task"));
while (!taskQueue.isEmpty()) {
Task task = taskQueue.take();
System.out.println("Processing " + task);
}
}
}
#Java #Training #Medium #PriorityBlockingQueue