Пріоритетна черга в Python
Пріоритетні черги це абстрактні структури даних, де кожне дані/значення в черзі мають певний пріоритет. Наприклад, в авіакомпаніях багаж під назвою 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))
