priority queue data structure c with illustration
Вступ до черги пріоритетів у C ++ з ілюстрацією.
Черга пріоритетів - це продовження черги, про яку ми вже говорили в нашому останньому посібнику.
Це схоже на чергу в певних аспектах, і все ж вона відрізняється від звичайної черги наступними пунктами:
- Кожен елемент у черзі пріоритетів пов'язаний з пріоритетом.
- Елемент з найвищим пріоритетом - це перший елемент, який буде видалено з черги.
- Якщо кілька пунктів мають однаковий пріоритет, то враховується порядок їх черги.
=> Клацніть тут, щоб переглянути абсолютну серію навчальних програм C ++.
Ми можемо візуалізувати чергу пріоритетів як модифіковану версію черги, за винятком того, що коли елемент повинен бути вилучений з черги, елемент з найвищим пріоритетом отримується першим. Тому ми вважаємо за краще використовувати черги пріоритетів замість черг, коли нам потрібно обробити елементи на основі пріоритету.
Що ви дізнаєтесь:
- Основні операції
- Ілюстрація
- Впровадження черг пріоритетів у C ++
- Застосування
- Висновок
- Рекомендована література
Основні операції
Давайте обговоримо деякі основні операції, що підтримуються чергою пріоритетів.
- Вставка (елемент, пріоритет): Вставляє елемент до черги пріоритетів із заданим пріоритетом.
- getHighestPriority (): Повертає елемент із найвищим пріоритетом.
- deleteHighestPriority (): Видаляє елемент із найвищим пріоритетом.
Окрім вищезазначених операцій, ми також можемо використовувати звичайні операції черги, такі як isEmpty (), isFull () та peek ().
Ілюстрація
Побачимо ілюстрацію черги пріоритетів. Для спрощення ми будемо використовувати символи ASCII як елементи в черзі пріоритетів. Чим вище значення ASCII, тим вищим є пріоритет.
Початковий стан - Черга пріоритетів (PQ) - {} => порожній
З наведеної вище ілюстрації ми бачимо, що операція вставки схожа на звичайну чергу. Але коли ми викликаємо “deleteHighestPriority” для черги пріоритетів, елемент з найвищим пріоритетом видаляється першим.
Отже, у перший раз, коли ми викликаємо цю функцію, елемент O видаляється, а вдруге елемент M видаляється, оскільки він має вищий пріоритет, ніж G та A.
Впровадження черг пріоритетів у C ++
Пріоритетні черги можуть бути реалізовані за допомогою:
# 1) Масиви / пов'язані списки
Ми можемо реалізувати пріоритетні черги за допомогою масивів, і це найпростіша реалізація для пріоритетних черг.
Щоб представити елементи в черзі пріоритетів, ми можемо просто оголосити структуру, як показано нижче:
struct pq_item{ int item; int priority; };Ми також заявили про пріоритет кожного товару.
Щоб вставити новий елемент до черги пріоритетів, нам просто потрібно вставити елемент в кінець масиву.
Щоб отримати елемент із черги, використовуючи getHighestPriority (), нам потрібно пройти масив від початку та повернути елемент з найвищим пріоритетом.
Подібним чином, щоб видалити елемент із черги за допомогою операції deleteHighestPriority, нам потрібно пройти весь масив і видалити елемент з найвищим пріоритетом. Потім перемістіть усі інші елементи після видаленого елемента на одну позицію назад.
Ми також можемо реалізувати чергу пріоритетів за допомогою пов'язаного списку. Ми можемо виконувати всі операції подібним чином, як масиви. Єдина відмінність полягає в тому, що нам не потрібно переміщати елементи після виклику deleteHighestPriority.
# 2) Купи
Використання купи для реалізації черги пріоритетів є найефективнішим способом і забезпечує набагато кращу продуктивність у порівнянні зі зв’язаними списками та масивами. На відміну від пов’язаного списку та масиву, реалізація купи займає час O (logn) для операцій вставки та видалення черги пріоритетів. Отримати операцію, getHighestPriority займає час O (1).
# 3) Вбудована черга пріоритетів у стандартній бібліотеці шаблонів (STL) у C ++
У C ++ ми маємо пріоритетну чергу як адаптивний клас контейнера, розроблений таким чином, що найвищим елементом є перший елемент у черзі, і всі елементи знаходяться в порядку зменшення.
Таким чином, кожен елемент у черзі пріоритетів має фіксований пріоритет.
У нас є клас у STL, який містить реалізацію черги пріоритетів.
Різні операції, що підтримуються чергою пріоритетів, є такими:
- приоритетна_черга :: розмір (): Повертає розмір черги.
- пріоритетна_черга :: порожня (): Перевіряє, чи черга порожня, і повертає свій статус.
- пріоритетна_черга :: top (): Повертає посилання на найвищий елемент черги пріоритетів.
- приоритетна_черга :: push (): Додає елемент в кінці черги пріоритетів.
- приоритетна_черга :: pop (): Видаляє перший елемент із черги пріоритетів.
- приоритетна_черга :: swap (): Використовується для обміну вмістом однієї черги пріоритетів на іншу тієї самої типу та розміру.
- тип значення черги пріоритету: Тип значення дає тип елемента, що зберігається в черзі пріоритетів. Це також діє як синонім параметра шаблону.
- приоритетна_черга :: emplace (): Використовується для вставки нового елемента в контейнер пріоритетної черги у верхній частині черги.
У наступній програмі ми побачимо функціональність черги пріоритетів у STL на C ++.
#include #include using namespace std; void displaypq(priority_queue pq) { priority_queue pqueue = pq; while (!pqueue.empty()) { cout << ' ' << pqueue.top(); pqueue.pop(); } cout << '
'; } int main () { priority_queue 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 << '
Top element of the queue(pq.top()): ' << pq.top(); cout << '
The priority queue pq is : '; displaypq(pq); cout << '
Priority queue, after pq.pop() operation : '; pq.pop(); displaypq(pq); return 0; } Вихід:
питання співбесіди для розробника .net
Розмір черги (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.
import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue PriorityQueue priority_Queue = new PriorityQueue(); // Adding items to the priority_Queue using add() priority_Queue.add(1); priority_Queue.add(3); priority_Queue.add(5); priority_Queue.add(7); // display the most priority element System.out.println('peek()::Head value:' + priority_Queue.peek()); // Print all elements in Priotity queue System.out.println('The priority queue:'); Iterator itr = priority_Queue.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ' '); // poll() function to remove the queue elements priority_Queue.poll(); System.out.println('
After poll() function, priority queue:'); Iterator itr2 = priority_Queue.iterator(); while (itr2.hasNext()) System.out.print(itr2.next() + ' '); // remove() function with priority queue priority_Queue.remove(5); System.out.println('
After Remove(5) function, priority queue:'); Iterator itr3 = priority_Queue.iterator(); while (itr3.hasNext()) System.out.print(itr3.next() + ' '); // Check if an element is present using contains() boolean b = priority_Queue.contains(3); System.out.println ( '
Priority queue contains 3?: ' + b); // use toArray() function to get objects from the queue and display the array elements Object() arr = priority_Queue.toArray(); System.out.println ( 'Array elements: '); for (int i = 0; i Вихід:
peek () :: Значення голови: 1
Черга пріоритетів:
1 3 5 7
Після функції poll (), пріоритетна черга:
3 7 5
Після функції Видалити (5) черга пріоритетів:
3 7
Черга пріоритетів містить 3 ?: true
Елементи масиву:
Значення: 3
Значення: 7
У наведеній вище програмі ми використовуємо клас PriorityQueue Java для створення об’єкта PriorityQueue, що містить об’єкт Integer. Ми додаємо елементи до черги за допомогою функції “add”. Потім викликається функція poll (), і вона видаляє елемент з передньої частини черги, що є найменшим елементом.
Знову ми викликаємо функцію “remove ()”, яка видаляє елемент, зазначений як параметр, з черги. Ми також використовуємо функцію “Містить ()”, щоб перевірити, чи присутній певний елемент у черзі. Нарешті, ми перетворюємо чергу в об’єкт масиву за допомогою функції “toArray ()”.
Застосування
- Обробники балансування навантаження операційної системи та обробників переривань: Функції операційної системи, такі як балансування навантаження та обробка переривань, реалізовані за допомогою пріоритетних черг. Діяльність балансування навантаження планує ресурси з найвищим пріоритетом, щоб ефективно виконувати наше балансування навантаження. Обробка переривань виконується шляхом обслуговування переривань з найвищим пріоритетом. Цю функціональність можна ефективно реалізувати за допомогою пріоритетних черг.
- Маршрут: Маршрутизація - це функція, яка використовується для маршрутизації мережевих ресурсів, щоб ми отримали максимальну пропускну здатність з мінімальним часом обробки. Це також можна реалізувати за допомогою черги пріоритетів.
- Невідкладна лікарня: У лікарні швидкої допомоги пацієнтів відвідують залежно від важкого стану пацієнта. Це можна змоделювати за допомогою пріоритетних черг.
- Найкоротший алгоритм Дейкстри: Тут графік зберігається як список суміжностей, і ми можемо використовувати чергу пріоритетів для ефективного вилучення мінімально зваженого краю зі списку суміжностей для реалізації найкоротшого алгоритму Дейкстри.
- Черга пріоритетів також може використовуватися для зберігання ключів вузла та вилучення мінімального вузла ключа під час реалізації охоплюючого дерева.
Висновок
Черги пріоритетів - це не що інше, як розширення черги. Але на відміну від черг, які додають / видаляють елементи за допомогою підходу FIFO, у черзі пріоритетів елементи видаляються з черги відповідно до пріоритету. Таким чином, кожен елемент у черзі асоціюється з пріоритетом, і елемент з найвищим пріоритетом є першим, що знімається з черги.
Черга пріоритетів має три основні операції, тобто insert (), getHighestPriority () та deleteHighestPriority (). Черга пріоритетів може бути реалізована за допомогою масивів або пов'язаного списку, але робота не дуже ефективна. Черга пріоритетів також може бути реалізована за допомогою купи, і продуктивність набагато швидша.
У C ++ ми також маємо клас контейнера, який реалізує функціональність черги пріоритетів. У Java існує вбудований клас priority_queue, який забезпечує функціональність черги пріоритетів.
Черга пріоритетів в основному використовується в додатках, які вимагають обробки елементів відповідно до пріоритету. Наприклад, він використовується при обробці переривань.
У нашому майбутньому підручнику буде розглянуто все про кругову чергу, яка є ще одним продовженням черги.
=> Відвідайте тут, щоб переглянути повний курс експертів на C ++.
Рекомендована література
- Структура даних черги в C ++ з ілюстрацією
- Черга пріоритетів у STL
- Структура даних стеку в C ++ з ілюстрацією
- Структура даних кругового зв’язаного списку на C ++ з ілюстрацією
- Структура даних зв’язаного списку на C ++ з ілюстрацією
- Подвійно пов’язана структура даних списку на C ++ з ілюстрацією
- Вступ до структур даних на C ++
- Як перевірити чергу обміну повідомленнями про програми: Підручник з IBM WebSphere MQ Intro