А Пріоритетна черга C++ є типом контейнерного адаптера, спеціально розробленого таким чином, що перший елемент черги є або найбільшим, або найменшим з усіх елементів у черзі, а елементи розташовані в порядку не зростання чи зменшення (тому ми бачимо, що кожен елемент черги має пріоритет {фіксований порядок}).
У C++ STL за замовчуванням верхній елемент завжди є найбільшим. Ми також можемо змінити його на найменший елемент у верхній частині. Пріоритетні черги будуються на вершині максимальної купи та використовують масив або вектор як внутрішню структуру. Простіше кажучи, Черга пріоритетів STL це реалізація C++
// C++ program to demonstrate the use of priority_queue> #include> #include> using> namespace> std;> // driver code> int> main()> {> >int> arr[6] = { 10, 2, 4, 8, 6, 9 };> >// defining priority queue> >priority_queue<>int>>pq;> >// printing array> >cout <<>'Array: '>;> >for> (>auto> i : arr) {> >cout << i <<>' '>;> >}> >cout << endl;> >// pushing array sequentially one by one> >for> (>int> i = 0; i <6; i++) {> >pq.push(arr[i]);> >}> >// printing priority queue> >cout <<>'Priority Queue: '>;> >while> (!pq.empty()) {> >cout << pq.top() <<>' '>;> >pq.pop();> >}> >return> 0;> }> |
>
>Вихід
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Максимальна черга пріоритету купи (схема за замовчуванням)
Як створити мінімальну купу для пріоритетної черги?
Як ми бачили раніше, пріоритетна черга реалізована як максимальна купа за замовчуванням у C++, але вона також надає нам можливість змінити її на мінімальну купу, передавши інший параметр під час створення пріоритетної черги.
Синтаксис:
priority_queue gq;>
де,
- ‘int’ — це тип елементів, які ви хочете зберегти в пріоритетній черзі. У цьому випадку це ціле число. Ви можете замінити внутр з будь-яким іншим необхідним типом даних. «вектор» — це тип внутрішнього контейнера, який використовується для зберігання цих елементів. std::priority_queue не є контейнером сам по собі, а застосовує контейнер. У нього загортаються інші контейнери. У цьому прикладі ми використовуємо a вектор , але ви можете вибрати інший контейнер, який підтримує методи front(), push_back() і pop_back().
- ' більше ' — це спеціальна функція порівняння. Це визначає порядок розташування елементів у пріоритетній черзі. У цьому конкретному прикладі більше встановлює a min-купа . Це означає, що найменший елемент буде у верхній частині черги.
У випадку максимальної купи нам не потрібно було вказувати їх, оскільки значення за замовчуванням уже підходять для максимальної купи.
приклад:
C++
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> >priority_queue<>int>, vector<>int>>, більше<>int>>> g)>> {> >while> (!g.empty()) {> >cout <<>' '> << g.top();> >g.pop();> >}> >cout <<>'
'>;> }> void> showArray(>int>* arr,>int> n)> {> >for> (>int> i = 0; i cout << arr[i] << ' '; } cout << endl; } // Driver Code int main() { int arr[6] = { 10, 2, 4, 8, 6, 9 }; priority_queue |
>
>Вихід
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
Мін. черга пріоритету купи
Примітка: Наведений вище синтаксис може бути важко запам’ятати, тому у випадку числових значень ми можемо помножити значення на -1 і використати максимальну купу, щоб отримати ефект мінімальної купи. Мало того, що ми можемо використовувати спеціальний метод сортування шляхом заміни більше з власною функцією порівняння.
Методи пріоритетної черги
Наступний список усіх методів класу std::priority_queue:
| метод | Визначення |
|---|---|
| priority_queue::empty() | Повертає, чи черга порожня. |
| priority_queue::size() | Повертає розмір черги. |
| priority_queue::top() | Повертає посилання на найвищий елемент черги. |
| priority_queue::push() | Додає елемент «g» у кінець черги. |
| priority_queue::pop() | Видаляє перший елемент черги. |
| priority_queue::swap() | Використовується для обміну вмістом двох черг за умови, що черги мають бути одного типу, хоча розміри можуть відрізнятися. |
| priority_queue::emplace() | Використовується для вставки нового елемента в контейнер пріоритетної черги. |
| priority_queue value_type | Представляє тип об’єкта, що зберігається як елемент у priority_queue. Він діє як синонім параметра шаблону. |
Операції над пріоритетною чергою в C++
1. Вставлення та видалення елементів пріоритетної черги
The push() метод використовується для вставки елемента в пріоритетну чергу. Щоб видалити елемент із черги пріоритетів, натисніть поп() використовується, тому що це видаляє елемент із найвищим пріоритетом.
Нижче наведено програму C++ для різних функцій у пріоритетній черзі:
C++
// C++ Program to demonstrate various> // method/function in Priority Queue> #include> #include> using> namespace> std;> // Implementation of priority queue> void> showpq(priority_queue<>int>>gq)> {> >priority_queue<>int>>g = gq;> >while> (!g.empty()) {> >cout <<>' '> << g.top();> >g.pop();> >}> >cout <<>'
'>;> }> // Driver Code> int> main()> {> >priority_queue<>int>>gquiz;> >// used in inserting the element> >gquiz.push(10);> >gquiz.push(30);> >gquiz.push(20);> >gquiz.push(5);> >gquiz.push(1);> >cout <<>'The priority queue gquiz is : '>;> > >// used for highlighting the element> >showpq(gquiz);> >// used for identifying the size> >// of the priority queue> >cout <<>'
gquiz.size() : '> <<> >gquiz.size();> >// used for telling the top element> >// in priority queue> >cout <<>'
gquiz.top() : '> <<> >gquiz.top();> >// used for popping the element> >// from a priority queue> >cout <<>'
gquiz.pop() : '>;> >gquiz.pop();> >showpq(gquiz);> >return> 0;> }> |
>
необхідна збірка ubuntu
>Вихід
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Зверніться до кінця для аналізу складності.
Примітка : Вище показано один із методів ініціалізації пріоритетної черги. Щоб дізнатися більше про ефективну ініціалізацію пріоритетної черги, натисніть тут.
2. Щоб отримати доступ до верхнього елемента черги пріоритетів
До верхнього елемента Пріоритетної черги можна отримати доступ за допомогою топ() метод.
C++
// C++ program to access the top> // element of priority queue> #include> #include> using> namespace> std;> // Driver code> int> main()> {> >// create a priority queue of int> >priority_queue<>int>>числа;> >// add items to priority_queue> >numbers.push(1);> >numbers.push(20);> >numbers.push(7);> >// get the element at the top> >cout <<>'Top element: '> <<> >numbers.top();> >return> 0;> }> |
>
>Вихід
Top element: 20>
Зверніться до кінця для аналізу складності.
Примітка: Ми можемо отримати доступ лише до верхнього елемента в черзі пріоритету.
3. Щоб перевірити, чи черга пріоритетів порожня чи ні:
Ми використовуємо метод empty(), щоб перевірити, чи порожня priority_queue. Цей метод повертає:
- True – повертається, коли пріоритетна черга порожня та позначається 1 False – створюється, коли пріоритетна черга не порожня або False і характеризується 0
приклад:
C++
java tostring
// C++ program to demonstrate> // Implementation of empty() function> #include> #include> using> namespace> std;> // Driver code> int> main()> {> >priority_queue<>int>>pqueueGFG;> >pqueueGFG.push(1);> > >// Priority Queue becomes 1> >// check if it is empty or not> >if> (pqueueGFG.empty())> >{> >cout <<>'Empty or true'>;> >}> >else> >{> >cout <<>'Contains element or False'>;> >}> >return> 0;> }> |
>
>Вихід
Contains element or False>
Зверніться до кінця для аналізу складності.
4. Щоб отримати/перевірити розмір черги пріоритетів
Він визначає розмір пріоритетної черги. Простіше кажучи, розмір() метод використовується для отримання кількості елементів, присутніх у Пріоритетна черга .
Нижче наведено програму C++ для перевірки розміру пріоритетної черги:
C++
// C++ program to demonstrate the> // size() method of priority queue> #include> #include> using> namespace> std;> // Driver code> int> main()> {> >// create a priority queue of string> >priority_queue pqueue;> >// add items to priority_queue> >pqueue.push(>'Geeks'>);> >pqueue.push(>'for'>);> >pqueue.push(>'Geeks'>);> >pqueue.push(>'C++'>);> >// get the size of queue> >int> size = pqueue.size();> >cout <<>'Size of the queue: '> << size;> >return> 0;> }> |
>
>Вихід
Size of the queue: 4>
Зверніться до кінця для аналізу складності.
5. Щоб поміняти вміст пріоритетної черги іншим подібного типу
Поміняти () Функція використовується для заміни вмісту однієї пріоритетної черги іншою пріоритетною чергою того самого типу та такого самого чи іншого розміру.
Нижче наведено програму C++ для обміну вмістом пріоритетної черги з іншою чергою подібного типу:
C++
// CPP program to illustrate> // Implementation of swap() function> #include> using> namespace> std;> // Print elements of priority queue> void> print(priority_queue<>int>>pq)> {> >while> (!pq.empty()) {> >cout << pq.top() <<>' '>;> >pq.pop();> >}> >cout << endl;> }> int> main()> {> >// priority_queue container declaration> >priority_queue<>int>>pq1;> >priority_queue<>int>>pq2;> >// pushing elements into the 1st priority queue> >pq1.push(1);> >pq1.push(2);> >pq1.push(3);> >pq1.push(4);> >// pushing elements into the 2nd priority queue> >pq2.push(3);> >pq2.push(5);> >pq2.push(7);> >pq2.push(9);> >cout <<>'Before swapping:-'> << endl;> >cout <<>'Priority Queue 1 = '>;> >print(pq1);> >cout <<>'Priority Queue 2 = '>;> >print(pq2);> >// using swap() function to swap elements of priority> >// queues> >pq1.swap(pq2);> >cout << endl <<>'After swapping:-'> << endl;> >cout <<>'Priority Queue 1 = '>;> >print(pq1);> >cout <<>'Priority Queue 2 = '>;> >print(pq2);> >return> 0;> }> // This code is contributed by Susobhan Akhuli> |
>
>Вихід
Before swapping:- Priority Queue 1 = 4 3 2 1 Priority Queue 2 = 9 7 5 3 After swapping:- Priority Queue 1 = 9 7 5 3 Priority Queue 2 = 4 3 2 1>
Зверніться до кінця для аналізу складності.
6. Вставити новий елемент у контейнер пріоритетної черги
Emplace() використовується для вставки нового елемента в контейнер черги пріоритетів, новий елемент додається до черги пріоритетів відповідно до його пріоритету. Це схоже на операцію натискання. Різниця полягає в тому, що операція emplace() зберігає непотрібну копію об’єкта.
Нижче наведено програму C++ для розміщення нового елемента в контейнері пріоритетної черги:
C++
// CPP program to illustrate> // Implementation of emplace() function> #include> using> namespace> std;> int> main()> {> >priority_queue<>int>>pq;> >pq.emplace(1);> >pq.emplace(2);> >pq.emplace(3);> >pq.emplace(4);> >pq.emplace(5);> >pq.emplace(6);> >// Priority queue becomes 1, 2, 3, 4, 5, 6> >// Printing the priority queue> >cout <<>'Priority Queue = '>;> >while> (!pq.empty()) {> >cout << pq.top() <<>' '>;> >pq.pop();> >}> >return> 0;> }> // This code is contributed by Susobhan Akhuli> |
>
>Вихід
Priority Queue = 6 5 4 3 2 1>
Зверніться до кінця для аналізу складності.
7. Щоб представити тип об’єкта, що зберігається як елемент у priority_queue
Метод priority_queue :: value_type — це вбудована функція в C++ STL, яка представляє тип об’єкта, що зберігається як елемент у priority_queue. Він діє як синонім параметра шаблону.
Синтаксис:
priority_queue::value_type variable_name>
Нижче наведено програму C++ для представлення типу об’єкта, що зберігається як елемент у priority_queue:
C++
// C++ program to illustrate the> // priority_queue :: value_type function> #include> using> namespace> std;> // Driver code> int> main()> {> >// declare integer value_type for priority queue> >priority_queue<>int>>::value_type AnInt;> >// declare string value_type for priority queue> >priority_queue::value_type AString;> >// Declares priority_queues> >priority_queue<>int>>q1;> >priority_queue q2;> >// Here AnInt acts as a variable of int data type> >AnInt = 20;> >cout <<>'The value_type is AnInt = '> << AnInt << endl;> >q1.push(AnInt);> >AnInt = 30;> >q1.push(AnInt);> >cout <<>'Top element of the integer priority_queue is: '> ><< q1.top() << endl;> >// here AString acts as a variable of string data type> >AString =>'geek'>;> >cout << endl> ><<>'The value_type is AString = '> << AString> ><< endl;> >q2.push(AString);> >AString =>'for'>;> >q2.push(AString);> >AString =>'geeks'>;> >q2.push(AString);> >cout <<>'Top element of the string priority_queue is: '> ><< q2.top() << endl;> >return> 0;> }> // This code is contributed by Susobhan Akhuli> |
>
shweta tiwari
>Вихід
The value_type is AnInt = 20 Top element of the integer priority_queue is: 30 The value_type is AString = geek Top element of the string priority_queue is: geeks>
Зверніться до кінця для аналізу складності.
Складності всіх операцій:
| методи | Складність часу | Допоміжний простір |
|---|---|---|
| priority_queue::empty() | О(1) | О(1) |
| priority_queue::size() | О(1) | О(1) |
| priority_queue::top() | О(1) | О(1) |
| priority_queue::push() | O(logN) | О(1) |
| priority_queue::pop() | O(logN) | О(1) |
| priority_queue::swap() | О(1) | O(N) |
| priority_queue::emplace() | O(logN) | О(1) |
| priority_queue value_type | О(1) | О(1) |