Меню

Структура на данните за приоритетна опашка в C ++ с илюстрация

  • Основен
  • Други
  • Структура на данните за приоритетна опашка в C ++ с илюстрация

priority queue data structure c with illustration

Опитайте Нашия Инструмент За Премахване На Проблемите

Въведение в приоритетната опашка в C ++ с илюстрация.

Priority Queue е разширение на опашката, което обсъдихме в последния ни урок.

Той е подобен на опашката в определени аспекти и въпреки това се различава от обикновената опашка в следните точки:

  • Всеки елемент в опашката с приоритет е свързан с приоритет.
  • Елементът с най-висок приоритет е първият елемент, който се премахва от опашката.
  • Ако повече от един елемент имат един и същ приоритет, тогава се взема предвид редът им в опашката.

=> Щракнете тук за абсолютната серия за обучение на 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, който съдържа изпълнението на приоритетната опашка.

Различните операции, поддържани от приоритетната опашка, са както следва:

  1. priority_queue :: size (): Връща размера на опашката.
  2. приоритетна_черта :: празно (): Проверява дали опашката е празна и връща нейното състояние.
  3. priority_queue :: top (): Връща препратка към най-горния елемент на опашката с приоритет.
  4. приоритетна_черта :: push (): Добавя елемент в края на опашката с приоритет.
  5. приоритетна_черта :: pop (): Премахва първия елемент от опашката с приоритет.
  6. priority_queue :: swap (): Използва се за размяна на съдържанието на една приоритетна опашка с друга от същия тип и размер.
  7. тип стойност на приоритетната опашка: Типът стойност дава типа на елемента, съхраняван в опашка с приоритет. Това също действа като синоним на параметъра на шаблона.
  8. priority_queue :: 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; }

Изход:

защо c ++ е по-добър от java

Размер на опашката (pq.size ()): 5
Най-горният елемент на опашката (pq.top ()): 9
Приоритетната опашка pq е: 9 7 5 3 1
Опашка с приоритет, след операция pq.pop (): 7 5 3 1

Внедряване на Java за приоритетна опашка

Приоритетна опашка в java е специална опашка, при която всички елементи в опашката са подредени според естественото подреждане или персонализирано подреждане с помощта на сравнител, доставен с опашката.

Опашката с приоритет в Java изглежда както е показано по-долу:

Внедряване на Java за приоритетна опашка

В приоритетната опашка на Java елементите са подредени така, че най-малкият елемент е в предната част на опашката, а най-големият елемент е в задната част на опашката. Така че, когато премахваме елемента от приоритетната опашка, той винаги е най-малкият елемент, който се премахва.

Класът, който реализира приоритетната опашка в Java, е “PriorityQueue” и е част от колекцията на Java. Той изпълнява интерфейса “Queue” на Java.

Следва йерархията на класовете за класа Java PriorityQueue.

йерархия на класа за клас 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
След функцията anketa (), приоритетна опашка:
3 7 5
След функцията Remove (5), приоритетна опашка:
3 7
Опашката за приоритет съдържа 3 ?: true
Елементи на масива:
Стойност: 3
Стойност: 7

В горната програма използваме класа PriorityQueue на Java, за да създадем обект от PriorityQueue, който съдържа обект Integer. Добавяме елементи в опашката с помощта на функцията „добавяне“. След това се извиква функцията poll () и тя изтрива елемента от предната страна на опашката, който се оказва най-малкият елемент.

Отново извикваме функцията “remove ()”, която премахва елемента, посочен като параметър, от опашката. Също така използваме функцията “Contains ()”, за да проверим дали даден елемент присъства в опашката. И накрая, преобразуваме опашката в обект на масив, използвайки функцията “toArray ()”.

Приложение

  • Манипулатори за балансиране на натоварването на операционната система и прекъсвания: Функциите на операционната система като балансиране на натоварването и обработка на прекъсвания се реализират с помощта на приоритетни опашки. Дейността по балансиране на натоварването планира ресурсите с най-висок приоритет, за да изпълнява ефективно нашето балансиране на товара. Обработката на прекъсванията се извършва чрез обслужване на прекъсванията с най-висок приоритет. Тази функционалност може ефективно да бъде приложена, като се използват приоритетните опашки.
  • Маршрут: Маршрутизацията е функция, която се използва за маршрутизиране на мрежовите ресурси, така че да получим максимална производителност с минимално време за изпълнение. Това може да се реализира и с помощта на приоритетната опашка.
  • Спешна помощ в болница: В спешното отделение на болницата пациентите се посещават според това колко тежко е състоянието на пациента. Това може да се симулира с помощта на приоритетни опашки.
  • Алгоритъм на най-краткия път на Dijkstra: Тук графиката се съхранява като списък за съседство и можем да използваме опашка с приоритет, за да извлечем ефективно минимално претегления ръб от списъка за съседство, за да приложим алгоритъма на най-краткия път на Dijkstra.
  • Приоритетната опашка може също да се използва за съхраняване на ключове на възли и извличане на минималния възел на ключ, докато се изпълнява обхващащо дърво.

Заключение

Приоритетните опашки не са нищо друго освен удължаването на опашката. Но за разлика от опашките, които добавят / премахват елементи, използвайки подхода FIFO, в приоритетната опашка елементите се премахват от опашката според приоритета. По този начин всеки елемент от опашката е свързан с приоритет и елементът с най-висок приоритет е първият, който се сваля от опашката.

Приоритетната опашка има три основни операции, т.е. insert (), getHighestPriority () и deleteHighestPriority (). Приоритетната опашка може да бъде изпълнена с помощта на масиви или свързан списък, но работата не е много ефективна. Приоритетната опашка може също да бъде внедрена с помощта на купчини и изпълнението е много по-бързо.

В C ++ имаме и клас контейнер, който реализира функционалността на приоритетна опашка. В Java има вграден клас priority_queue, който осигурява функционалността на приоритетна опашка.

Опашката за приоритет се използва главно в приложения, които изискват елементите да бъдат обработени според приоритета. Например, той се използва при обработка на прекъсвания.

Нашият предстоящ урок ще разгледа всичко за кръговата опашка, която е още едно разширение на опашката.

=> Посетете тук за пълния курс на C ++ от експерти.

Препоръчително четене

^