Приоритетная очередь — это расширение очереди, которую мы обсуждали в нашей предыдущей статье.
В некоторых аспектах она похожа на очередь, но отличается от обычной очереди следующими моментами:
- Каждый элемент в приоритетной очереди связан с приоритетом.
- Элемент с наивысшим приоритетом является первым элементом, который будет удален из очереди.
- Если более одного элемента имеют одинаковый приоритет, то учитывается их порядок в очереди.
Мы можем визуализировать приоритетную очередь как модифицированную версию очереди, за исключением того, что, когда элемент должен быть удален из очереди, элемент с наивысшим приоритетом извлекается первым. Поэтому мы предпочитаем использовать приоритетные очереди вместо обычной очереди, когда нам нужно обрабатывать элементы на основе приоритета.
Основные операции
Давайте обсудим некоторые из основных операций, поддерживаемых приоритетной очередью:
- Insert(item, priority): вставляет элемент в приоритетную очередь с заданным приоритетом.
- getHighestPriority(): возвращает элемент с наивысшим приоритетом.
- deleteHighestPriority(): удаляет элемент с наивысшим приоритетом.
Помимо вышеуказанных операций, мы также можем использовать обычные операции с очередью, такие как isEmpty (), isFull () и peek ().
Демонстрация
Давайте рассмотрим схему приоритетной очереди. Для простоты мы будем использовать символы ASCII в качестве элементов в приоритетной очереди. Чем выше значение ASCII, тем выше приоритет.
Начальное состояние – Приоритетная очередь (PQ) – {} => empty
Из приведенной выше схемы видно, что операция вставки похожа на обычную очередь. Но когда мы вызываем “deleteHighestPriority” для приоритетной очереди, элемент с наивысшим приоритетом удаляется первым.
Следовательно, в первый раз, когда мы вызываем эту функцию, элемент O удаляется, а во второй раз удаляется элемент M, поскольку он имеет более высокий приоритет, чем G и A.
Реализация приоритетной очереди на C++
Приоритетные очереди могут быть реализованы с помощью:
1) Массивов / связных списков
Мы можем реализовать приоритетные очереди, используя массивы, и это самая простая реализация для приоритетных очередей.
Чтобы представить элементы в приоритетной очереди, мы можем просто объявить структуру, как показано ниже:
| struct pq_item{ int item; int priority; }; |
Мы также объявили приоритет для каждого элемента.
Чтобы вставить новый элемент в приоритетную очередь, нам просто нужно вставить элемент в конец массива.
Чтобы получить элемент из очереди с помощью getHighestPriority () , нам нужно пройти по массиву с самого начала и вернуть элемент с наивысшим приоритетом.
Аналогично, чтобы удалить элемент из очереди с помощью операции deleteHighestPriority, нам нужно пройти весь массив и удалить элемент с наивысшим приоритетом. Затем переместить все остальные элементы после удаленного элемента на одну позицию назад.
Мы также можем реализовать приоритетную очередь, используя связный список. Мы можем выполнять все операции аналогично массивам. Единственное отличие состоит в том, что нам не нужно перемещать элементы после вызова deleteHighestPriority .
2) Кучи
Использование куч для реализации приоритетной очереди является наиболее эффективным способом и обеспечивает намного лучшую производительность по сравнению со связными списками и массивами. В отличие от связного списка и массива, реализация кучи занимает O (logn) времени для операций вставки и удаления приоритетной очереди. Операция Get, getHighestPriority занимает O (1) времени.
3) Встроенной приоритетной очереди в стандартной библиотеке шаблонов (STL) в C++
В C++ есть приоритетная очередь в виде адаптивного класса контейнера, спроектированного таким образом, что самый высокий элемент является первым элементом в очереди, а все элементы расположены в порядке убывания.
Таким образом, каждый элемент в приоритетной очереди имеет фиксированный приоритет.
У нас есть класс <queue> в STL, который содержит реализацию приоритетной очереди.
Различные операции, поддерживаемые приоритетной очередью, следующие:
- priority_queue::size(): возвращает размер очереди.
- priority_queue::empty(): проверяет, пуста ли очередь, и возвращает ее статус.
- priority_queue:: top(): возвращает ссылку на самый верхний элемент приоритетной очереди.
- priority_queue::push(): добавляет элемент в конец приоритетной очереди.
- priority_queue::pop(): удаляет первый элемент из приоритетной очереди.
- priority_queue:: swap (): используется для замены содержимого одной приоритетной очереди на другую такого же типа и размера.
- priority queue value type: тип значения задает тип элемента, хранящегося внутри приоритетной очереди. Это также действует как синоним параметра шаблона.
- priority_queue:: emplace (): используется для вставки нового элемента в контейнер приоритетной очереди в верхней части очереди.
В следующей программе мы покажем функциональность приоритетной очереди в STL в C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <queue> using namespace std; void displaypq(priority_queue <int> pq) { priority_queue <int> pqueue = pq; while (!pqueue.empty()) { cout << '\t' << pqueue.top(); pqueue.pop(); } cout << '\n'; } int main () { priority_queue <int> pq; pq.push(1); pq.push(3); pq.push(5); pq.push(7); pq.push(9); cout << "Size of the queue(pq.size()): " << pq.size(); cout << "\nTop element of the queue(pq.top()): " << pq.top(); cout << "\nThe priority queue pq is : "; displaypq(pq); cout << "\nPriority queue, after pq.pop() operation : "; pq.pop(); displaypq(pq); return 0; } |
Вывод данных:
| Размер очереди (pq.size()): 5 Верхний элемент очереди (pq.top()): 9 Приоритетная очередь pq равна: 9 7 5 3 1 Приоритетная очередь, после операции pq.pop() : 7 5 3 1 |
Реализация приоритетной очереди на Java
Приоритетная очередь в java — это специальная очередь, в которой все элементы в очереди упорядочены в соответствии с естественным порядком или пользовательским порядком с использованием компаратора, поставляемого с очередью.
Приоритетная очередь в Java выглядит так, как показано ниже:
В приоритетной очереди в Java элементы расположены таким образом, что наименьший элемент находится в начале очереди, а наибольший элемент находится в конце очереди. Поэтому, когда мы удаляем элемент из приоритетной очереди, это всегда самый маленький элемент, который удаляется.
Класс, который реализует приоритетную очередь в Java, называется “PriorityQueue” и является частью инфраструктуры коллекций Java. Он реализует интерфейс Java ”Queue».
Ниже приведена иерархия классов для класса Java PriorityQueue:
Ниже приведен пример функциональности приоритетной очереди с целыми числами в качестве элементов на Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
import java.util.*; class Main { public static void main(String args[]) { // Создать пустую приоритетную очередь PriorityQueue<Integer> priority_Queue = new PriorityQueue<Integer>(); // Добавление элементов в priority_Queue с помощью add() priority_Queue.add(1); priority_Queue.add(3); priority_Queue.add(5); priority_Queue.add(7); // отображение наиболее приоритетного элемента System.out.println("peek()::Head value:" + priority_Queue.peek()); // Печать всех элементов в очереди Priotity System.out.println("The priority queue:"); Iterator itr = priority_Queue.iterator(); while (itr.hasNext()) System.out.print(itr.next() + " "); // функция poll() для удаления элементов очереди priority_Queue.poll(); System.out.println("\nAfter poll() function, priority queue:"); Iterator<Integer> itr2 = priority_Queue.iterator(); while (itr2.hasNext()) System.out.print(itr2.next() + " "); // функция remove() с приоритетной очередью priority_Queue.remove(5); System.out.println("\n\nAfter Remove(5) function, priority queue:"); Iterator<Integer> itr3 = priority_Queue.iterator(); while (itr3.hasNext()) System.out.print(itr3.next() + " "); // Проверьте, присутствует ли элемент, используя contains() boolean b = priority_Queue.contains(3); System.out.println ( "\nPriority queue contains 3?: " + b); // используйте функцию toArray() для получения объектов из очереди и отображения элементов массива Object[] arr = priority_Queue.toArray(); System.out.println ( "Array elements: "); for (int i = 0; i<arr.length; i++) System.out.println ( "Value: " + arr[i].toString()) ; } } |
Вывод данных:
| peek()::Head value:1 The priority queue: 1 3 5 7 After poll() function, priority queue: 3 7 5 After Remove(5) function, priority queue: 3 7 Priority queue contains 3?: true Array elements: Value: 3 Value: 7 |
В приведенной выше программе мы используем класс PriorityQueue Java для создания объекта PriorityQueue, который содержит целочисленный объект. Мы добавляем элементы в очередь, используя функцию “добавить”. Затем вызывается функция poll(), которая удаляет элемент из начала очереди, который является наименьшим элементом.
Снова мы вызываем функцию “remove ()”, которая удаляет элемент, указанный в качестве параметра, из очереди. Мы также используем функцию “Contains ()”, чтобы проверить, присутствует ли определенный элемент в очереди. Наконец, мы преобразуем очередь в объект массива с помощью функции “toArray ()”.
Применение
- Балансировка нагрузки операционной системы и обработчики прерываний: функции операционной системы, такие как балансировка нагрузки и обработка прерываний, реализуются с использованием приоритетной очереди. Операция балансировки нагрузки выбирает ресурсы с наивысшим приоритетом, чтобы эффективней выполнять нашу балансировку нагрузки. Обработка прерываний выполняется путем обслуживания прерываний с наивысшим приоритетом. Эта функциональность может быть эффективно реализована с использованием приоритетной очереди.
- Маршрутизация: маршрутизация — это функция, которая используется для маршрутизации сетевых ресурсов таким образом, чтобы мы получали максимальную пропускную способность при минимальном времени выполнения. Это также может быть реализовано с использованием приоритетной очереди.
- Неотложная помощь в больнице: в отделении неотложной помощи пациенты обслуживаются в зависимости от того, насколько тяжелым является состояние пациента. Такое можно смоделировать с использованием приоритетной очереди.
- Алгоритм кратчайшего пути Дейкстры: здесь график хранится в виде списка смежности, и мы можем использовать приоритетную очередь для эффективного извлечения минимального взвешенного ребра из списка смежности для реализации алгоритма кратчайшего пути Дейкстры.
- Приоритетная очередь также может использоваться для хранения ключей узла и извлечения узла с минимальным ключом при реализации связующего дерева.
Итог
Приоритетные очереди — это не что иное, как расширение обычной очереди. Но в отличие от очередей, которые добавляют / удаляют элементы с использованием подхода FIFO, в приоритетной очереди элементы удаляются из очереди в соответствии с приоритетом. Таким образом, каждый элемент в очереди связан с приоритетом, и элемент с наивысшим приоритетом является первым, который будет удален из очереди.
Приоритетная очередь имеет три основные операции, т.е. insert (), getHighestPriority () и deleteHighestPriority () . Приоритетная очередь может быть реализована с использованием массивов или связных списков, но работа ее не очень эффективна. Приоритетная очередь также может быть реализована с использованием куч, из-за чего производительность будет намного выше.
В C++ также есть класс контейнера <queue>, который реализует функциональность приоритетной очереди. В Java есть встроенный класс priority_queue, который обеспечивает функциональность приоритетной очереди.
Приоритетная очередь в основном используется в приложениях, которые требуют, чтобы элементы обрабатывались в соответствии с приоритетом. Например, она используется при обработке прерываний.
В нашей следующей статье мы поговорим о структуре данных циклической очереди в C++.
С Уважением, МониторБанк