Java for Beginner

PriorityQueue, принципы работы и внутреннее устройство

PriorityQueue — это класс из пакета java.util, который реализует интерфейс Queue. В отличие от обычной очереди (FIFO), PriorityQueue основана на приоритетах элементов. Приоритет определяется с помощью естественного порядка элементов или через предоставленный компаратор.

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        priorityQueue.add(4);
        priorityQueue.add(1);
        priorityQueue.add(3);

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

В этом примере PriorityQueue автоматически упорядочивает элементы, так что при удалении элементов они извлекаются в порядке возрастания: 1, 3, 4.

Принципы работы PriorityQueue

Естественный порядок или компаратор: Элементы могут упорядочиваться на основе их естественного порядка (если элементы реализуют интерфейс Comparable) или на основе компаратора, предоставленного при создании очереди.
Бинарная куча (Binary Heap): Внутренняя реализация PriorityQueue основана на бинарной куче, которая является частично упорядоченным двоичным деревом. Это позволяет эффективно добавлять элементы и извлекать минимальный элемент.
Время выполнения операций: Основные операции PriorityQueue (вставка, удаление минимального элемента) выполняются за логарифмическое время O(log n), где n — количество элементов в очереди.

Внутреннее устройство PriorityQueue

PriorityQueue использует массив для хранения элементов, которые упорядочиваются в соответствии с правилами бинарной кучи. Дочерние элементы имеют более низкий приоритет по сравнению с родительскими элементами.

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable {
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    private Object[] queue;
    private int size;
    private final Comparator<? super E> comparator;

    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

    public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

    // Основные методы: add, poll, offer, remove, etc.
}

Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://www.baeldung.com/java-priorityqueue
https://sky.pro/media/ispolzovanie-priorityqueue-v-java/

#Java #Training #Medium #PriorityQueue

Baeldung

Guide to Java PriorityQueue | Baeldung

A quick and practical guide to Java's PriorityQueue.

179 viewsДен, 05:13

Java for Beginner

Основные методы PriorityQueue и примеры использования

add(E e):
Добавляет элемент в очередь. Если элемент null, выбрасывает NullPointerException.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(20);
pq.add(15);

offer(E e):
Добавляет элемент в очередь. Возвращает true, если элемент был успешно добавлен, и false в противном случае.

pq.offer(5);

poll():
Возвращает и удаляет элемент с наивысшим приоритетом (минимальный элемент). Возвращает null, если очередь пуста.

Integer top = pq.poll(); // Возвращает 5 и удаляет его из очереди

peek():
Возвращает элемент с наивысшим приоритетом, но не удаляет его. Возвращает null, если очередь пуста.

Integer top = pq.peek(); // Возвращает 10, но не удаляет его

remove(Object o):
Удаляет указанный элемент из очереди, если он присутствует. Возвращает true, если элемент был успешно удален, и false в противном случае.

boolean removed = pq.remove(15); // Удаляет элемент 15

contains(Object o):
Проверяет, присутствует ли указанный элемент в очереди. Возвращает true, если элемент найден, и false в противном случае.

boolean contains = pq.contains(20); // Проверяет наличие элемента 20

size():
Возвращает количество элементов в очереди.

int size = pq.size(); // Возвращает количество элементов в очереди

Примеры использования

Реализация задачи с приоритетом:

import java.util.PriorityQueue;
import java.util.Comparator;

class Task {
    private String name;
    private int priority;

    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    public int getPriority() {
        return priority;
    }

    @Override
    public String toString() {
        return name + ": " + priority;
    }
}

class TaskComparator implements Comparator<Task> {
    public int compare(Task t1, Task t2) {
        return Integer.compare(t1.getPriority(), t2.getPriority());
    }
}

public class TaskScheduler {
    public static void main(String[] args) {
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(new TaskComparator());

        taskQueue.add(new Task("Task 1", 2));
        taskQueue.add(new Task("Task 2", 1));
        taskQueue.add(new Task("Task 3", 3));

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

Использование с Comparator для обратного порядка:

PriorityQueue<Integer> reversePQ = new PriorityQueue<>(Comparator.reverseOrder());

reversePQ.add(10);
reversePQ.add(20);
reversePQ.add(15);

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

Модель с приоритетом задач на основе времени выполнения:

import java.util.PriorityQueue;

class Job implements Comparable<Job> {
    private String jobName;
    private int executionTime;

    public Job(String jobName, int executionTime) {
        this.jobName = jobName;
        this.executionTime = executionTime;
    }

    @Override
    public int compareTo(Job other) {
        return Integer.compare(this.executionTime, other.executionTime);
    }

    @Override
    public String toString() {
        return jobName + ": " + executionTime;
    }
}

public class JobScheduler {
    public static void main(String[] args) {
        PriorityQueue<Job> jobQueue = new PriorityQueue<>();

        jobQueue.add(new Job("Job 1", 30));
        jobQueue.add(new Job("Job 2", 10));
        jobQueue.add(new Job("Job 3", 20));

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

#Java #Training #Medium #PriorityQueue

194 viewsДен, 14:00

About

Blog

Apps

Platform