Пріоритетні черги це абстрактні структури даних, де кожне дані/значення в черзі мають певний пріоритет. Наприклад, в авіакомпаніях багаж під назвою Business або First-class прибуває раніше за інших.
Пріоритетна черга — це розширення черги з такими властивостями.
- Елемент з високим пріоритетом вилучається з черги перед елементом з низьким пріоритетом.
- Якщо два елементи мають однаковий пріоритет, вони обслуговуються відповідно до свого порядку в черзі.
різноманітні програми Пріоритетної черги в інформатиці є:
Алгоритми планування завдань, планування процесора та диска, керування ресурсами, які спільно використовуються різними процесами тощо.
Ключові відмінності між пріоритетною чергою та чергою:
- У Queue найстаріший елемент вилучається з черги першим. Тоді як у пріоритетній черзі елемент, заснований на найвищому пріоритеті, виключається з черги.
- Коли елементи вириваються з черги пріоритету, отриманий результат сортується або в порядку зростання, або в порядку зменшення. Тоді як, коли елементи витягуються з простої черги, у результаті отримується порядок даних FIFO.
Нижче a проста реалізація пріоритетної черги.
Python
# A simple implementation of Priority Queue> # using Queue.> class> PriorityQueue(>object>):> >def> __init__(>self>):> >self>.queue>=> []> >def> __str__(>self>):> >return> ' '>.join([>str>(i)>for> i>in> self>.queue])> ># for checking if the queue is empty> >def> isEmpty(>self>):> >return> len>(>self>.queue)>=>=> 0> ># for inserting an element in the queue> >def> insert(>self>, data):> >self>.queue.append(data)> ># for popping an element based on Priority> >def> delete(>self>):> >try>:> >max_val>=> 0> >for> i>in> range>(>len>(>self>.queue)):> >if> self>.queue[i]>>self>.queue[max_val]:> >max_val>=> i> >item>=> self>.queue[max_val]> >del> self>.queue[max_val]> >return> item> >except> IndexError:> >print>()> >exit()> if> __name__>=>=> '__main__'>:> >myQueue>=> PriorityQueue()> >myQueue.insert(>12>)> >myQueue.insert(>1>)> >myQueue.insert(>14>)> >myQueue.insert(>7>)> >print>(myQueue)> >while> not> myQueue.isEmpty():> >print>(myQueue.delete())> |
>
>Вихід:
12 1 14 7 14 12 7 1>
Зауважте, що часова складність видалення становить O(n) у наведеному вище коді. А краща реалізація це використовувати Бінарна купа який зазвичай використовується для реалізації пріоритетної черги. Зауважте, що Python надає heapq в бібліотеці також.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))>