Пріоритетна черга — це абстрактний тип даних, який поводиться подібно до звичайної черги, за винятком того, що кожен елемент має певний пріоритет, тобто елемент із найвищим пріоритетом буде першим у черзі пріоритету. Пріоритет елементів у черзі пріоритетів визначатиме порядок, у якому елементи видаляються з черги пріоритетів.
Пріоритетна черга підтримує лише порівнювані елементи, що означає, що елементи впорядковані в порядку зростання або спадання.
порівняти рядок java
Наприклад, припустімо, що ми маємо такі значення, як 1, 3, 4, 8, 14, 22, вставлені в чергу пріоритетів із порядком значень від найменшого до найбільшого. Таким чином, число 1 матиме найвищий пріоритет, а число 22 – найнижчий.
Характеристики пріоритетної черги
Пріоритетна черга — це розширення черги, що містить такі характеристики:
- Кожен елемент у черзі пріоритету має певний пріоритет, пов’язаний з ним.
- Елемент із вищим пріоритетом буде видалено перед видаленням елемента з меншим пріоритетом.
- Якщо два елементи в черзі пріоритету мають однаковий пріоритет, вони будуть організовані за принципом FIFO.
Давайте розберемося з пріоритетною чергою на прикладі.
У нас є пріоритетна черга, яка містить такі значення:
1, 3, 4, 8, 14, 22
Усі значення розташовані в порядку зростання. Тепер подивимося, як буде виглядати пріоритетна черга після виконання наступних операцій:
Типи пріоритетної черги
Існує два типи черги пріоритету:
Відображення пріоритетної черги
Тепер ми побачимо, як представити чергу пріоритетів через односторонній список.
Ми створимо пріоритетну чергу за допомогою наведеного нижче списку, у якому ІНФО список містить елементи даних, PRN список містить номери пріоритетів кожного елемента даних, доступного в ІНФО список, а LINK в основному містить адресу наступного вузла.
Давайте крок за кроком створимо пріоритетну чергу.
java sort arraylist
У разі пріоритетної черги номер із нижчим пріоритетом вважається вищим пріоритетом, тобто нижчий номер пріоритету = вищий пріоритет.
Крок 1: У списку номер нижчого пріоритету – 1, значення даних якого – 333, тому його буде вставлено в список, як показано на схемі нижче:
крок 2: Після вставки 333 пріоритет номер 2 має вищий пріоритет, а значення даних, пов’язані з цим пріоритетом, становлять 222 і 111. Отже, ці дані буде вставлено на основі принципу FIFO; тому спочатку буде додано 222, а потім 111.
крок 3: Після вставки елементів пріоритету 2 наступним номером вищого пріоритету буде 4, а елементи даних, пов’язані з 4 номерами пріоритету, – 444, 555, 777. У цьому випадку елементи будуть вставлені на основі принципу FIFO; тому спочатку буде додано 444, потім 555, а потім 777.
крок 4: Після вставки елементів із пріоритетом 4 наступним номером із вищим пріоритетом буде 5, а значення, пов’язане з пріоритетом 5, – 666, тому його буде вставлено в кінець черги.
Реалізація пріоритетної черги
Пріоритетну чергу можна реалізувати чотирма способами, які включають масиви, пов’язаний список, структуру даних купи та бінарне дерево пошуку. Структура даних купи є найефективнішим способом реалізації черги пріоритетів, тому в цьому розділі ми реалізовуватимемо чергу пріоритетів за допомогою структури даних купи. Тепер спочатку ми зрозуміємо, чому купа є найефективнішим способом серед усіх інших структур даних.
Аналіз складності з використанням різних реалізацій
| Реалізація | додати | видалити | підглядати |
| Зв'язаний список | O(1) | O(n) | O(n) |
| Двійкова купа | O (вхід) | O (вхід) | O(1) |
| Двійкове дерево пошуку | O (вхід) | O (вхід) | O(1) |
Що таке Heap?
Купа — це структура даних на основі дерева, яка утворює повне бінарне дерево та задовольняє властивість купи. Якщо A є батьківським вузлом B, тоді A впорядковується відносно вузла B для всіх вузлів A і B у купі. Це означає, що значення батьківського вузла може бути більше або дорівнювати значенню дочірнього вузла, або значення батьківського вузла може бути менше або дорівнювати значенню дочірнього вузла. Тому можна сказати, що купи бувають двох типів:
Обидві купи є бінарною купою, оскільки кожна має рівно два дочірніх вузла.
Пріоритетні операції в черзі
Загальні операції, які ми можемо виконувати в пріоритетній черзі, це вставка, видалення та перегляд. Давайте подивимося, як ми можемо підтримувати структуру даних купи.
Якщо ми вставимо елемент у пріоритетну чергу, він переміститься у порожній слот, дивлячись зверху вниз і зліва направо.
Якщо елемент знаходиться не в правильному місці, тоді він порівнюється з батьківським вузлом; якщо він виявлений не в порядку, елементи міняються місцями. Цей процес триває до тих пір, поки елемент не буде розміщено в правильному положенні.
Як ми знаємо, що в максимальній купі максимальний елемент є кореневим вузлом. Коли ми видаляємо кореневий вузол, він створює порожній слот. У цей порожній слот буде додано останній вставлений елемент. Потім цей елемент порівнюється з дочірніми вузлами, тобто лівим і правим дочірніми вузлами, і міняється місцями з меншим із двох. Він продовжує рух вниз по дереву, доки не буде відновлено властивість купи.
Заявки Пріоритетної черги
Нижче наведено програми пріоритетної черги:
dateformat.format java
- Він використовується в алгоритмі найкоротшого шляху Дейкстри.
- Він використовується в алгоритмі прима
- Він використовується в техніках стиснення даних, таких як код Хаффмана.
- Використовується при сортуванні купи.
- Він також використовується в операційній системі, як пріоритетне планування, балансування навантаження та обробка переривань.
Програма для створення пріоритетної черги за допомогою бінарної максимальної купи.
#include #include int heap[40]; int size=-1; // retrieving the parent node of the child node int parent(int i) { return (i - 1) / 2; } // retrieving the left child of the parent node. int left_child(int i) { return i+1; } // retrieving the right child of the parent int right_child(int i) { return i+2; } // Returning the element having the highest priority int get_Max() { return heap[0]; } //Returning the element having the minimum priority int get_Min() { return heap[size]; } // function to move the node up the tree in order to restore the heap property. void moveUp(int i) { while (i > 0) { // swapping parent node with a child node if(heap[parent(i)] <heap[i]) 2 { int temp; temp="heap[parent(i)];" heap[parent(i)]="heap[i];" heap[i]="temp;" } updating the value of i to function move node down tree in order restore heap property. void movedown(int k) index="k;" getting location left child if (left heap[index]) right (right k is not equal (k !="index)" heap[index]="heap[k];" heap[k]="temp;" movedown(index); removing element maximum priority removemax() r="heap[0];" heap[0]="heap[size];" size="size-1;" movedown(0); inserting a queue insert(int p) + 1; heap[size]="p;" up maintain property moveup(size); from at given i. delete(int i) stored ith shifted root moveup(i); having removemax(); main() elements insert(20); insert(19); insert(21); insert(18); insert(12); insert(17); insert(15); insert(16); insert(14); printf('elements are : '); for(int printf('%d ',heap[i]); delete(2); deleting whose 2. printf('
elements after max="get_Max();" printf('
the which highest %d: ',max); min="get_Min();" minimum %d',min); return 0; < pre> <p> <strong>In the above program, we have created the following functions:</strong> </p> <ul> <tr><td>int parent(int i):</td> This function returns the index of the parent node of a child node, i.e., i. </tr><tr><td>int left_child(int i):</td> This function returns the index of the left child of a given index, i.e., i. </tr><tr><td>int right_child(int i):</td> This function returns the index of the right child of a given index, i.e., i. </tr><tr><td>void moveUp(int i):</td> This function will keep moving the node up the tree until the heap property is restored. </tr><tr><td>void moveDown(int i):</td> This function will keep moving the node down the tree until the heap property is restored. </tr><tr><td>void removeMax():</td> This function removes the element which is having the highest priority. </tr><tr><td>void insert(int p):</td> It inserts the element in a priority queue which is passed as an argument in a function <strong>.</strong> </tr><tr><td>void delete(int i):</td> It deletes the element from a priority queue at a given index. </tr><tr><td>int get_Max():</td> It returns the element which is having the highest priority, and we know that in max heap, the root node contains the element which has the largest value, and highest priority. </tr><tr><td>int get_Min():</td> It returns the element which is having the minimum priority, and we know that in max heap, the last node contains the element which has the smallest value, and lowest priority. </tr></ul> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/what-is-priority-queue-9.webp" alt="Priority Queue"> <hr></heap[i])>