Автор оригинала: Team Python Pool.

Понимание приоритетной очереди в Python с реализацией

Вы устали слышать некоторые странные концепции структур данных, такие как priority queue? Больше никаких путаниц, потому что здесь вы узнаете все о приоритетной очереди. И мы будем использовать язык Python для написания некоторого кода, так что давайте скажем более конкретно Python priority queue. Мы будем использовать Python 3. Многие люди, которые только начали изучать такие термины структуры данных, как очередь, стек, куча и приоритетная очередь, обычно путают между кучей и приоритетной очередью. Поэтому мы поговорим об их различиях и сходствах.

Приоритетная очередь в Python или любом другом языке-это особый тип очереди, в которой каждый элемент связан с приоритетом и обслуживается в соответствии с его предпочтениями. Если встречаются элементы с одинаковым приоритетом, то они выполняются в соответствии с их порядком в очереди. Как правило, для присвоения приоритета учитывается значение самого элемента.

Что такое глубокая очередь приоритетов

Проще говоря, приоритетная очередь-это ADT, похожий на очередь в структуре данных (очень важный предмет CS major). Но что отличает его от очереди, так это то, что элементы в приоритетной очереди имеют некоторый приоритет над другими элементами.

Что означает для нас приоритет этих элементов? Действительно ли они стоят моего времени? Да. Важно знать, почему они существуют, если вы готовы изучать и осваивать приоритетную очередь и другие ее аспекты, такие как Python priority queue comparator или priority queue max size в python и т. Д. Они просто существуют, потому что приоритет определяет порядок удаления этих элементов в очереди приоритетов.

Очередь (структура данных) использует FITFLOP, но приоритетная очередь не удаляет свои элементы на основе их прибытия.

Итак, теперь, когда вы изучили основное определение и термины приоритетной очереди. Давайте перейдем глубже и рассмотрим некоторые операции с приоритетной очередью Python. Каковы некоторые из основных или популярных операций, выполняемых в приоритетной очереди? Мы можем перебирать нашу приоритетную очередь или выполнять сортировку по ней. А также можно также изменить приоритет элементов в Pythonn priority queue или мы увидим некоторые операции, такие как Python priority queue, уменьшающие ключ или обновляющие значения.

Как мы можем реализовать Приоритетную очередь в Python

Существует множество способов реализации приоритетной очереди в Python. Но в этом уроке мы поговорим о трех лучших способах реализации приоритетной очереди в Python.

• Python сортированный список
• Использование модуля heapq
• Использование очереди .PriorityQueue

Реализация Приоритетной Очереди С Использованием Отсортированного Списка

Давайте начнем с простого и легкого способа. Таким образом, мы будем использовать стандартный список, но нам нужно сортировать этот список каждый раз, когда добавляется элемент.

Давайте рассмотрим пример приоритетной очереди с использованием списков.

Пример 1:

Предположим, мы хотим создать приоритетную очередь, которая хранит порядок студентов, которые должны быть допущены на семинар первыми. Затем мы можем использовать следующий код для создания приоритетной очереди с помощью списков:

student_pass = []

student_pass.append((3, 'Ram'))
student_pass.append((1, 'Sham'))
student_pass.append((2, 'Vasu'))

# NOTE: Remember to re-sort every time
#       a new element is inserted, or use
#       bisect.insort().
)

while student_pass:
.pop()
	print(item)

Выход:

(1, 'Sham')
(2, 'Vasu')
(3, 'Ram')

Временная сложность Приоритетной очереди С использованием Отсортированного списка

Поддержание порядка путем добавления в список и повторной сортировки также занимает не менее O(n log n) времени. Таким образом, он эффективен только тогда, когда нам нужно сделать несколько вставок.

Реализация Приоритетной очереди С использованием модуля heapq

Прежде чем приступить к реализации и перейти непосредственно к примерам. Мы должны знать все строительные блоки структуры, то есть кучу, очередь, приоритетную очередь и т. Д.

Что такое куча и приоритетная очередь в Python?

Итак, приоритетная очередь реализована в Python (не только в Python) с использованием двоичной кучи, или вы бы сказали, что это очередь кучи (heapq ниже в этой статье).

Что такое куча(heapq) ?

Куча-это древовидная структура данных, также известная как приоритет кучи. (Простыми словами, вы можете сказать, что приоритетная очередь в Python использует кучу для классификации элементов)

Что такое очередь ?

Очередь

Очередь людей, представьте себе, что кто-то держит премиальный пропуск, поэтому ему/ей будет предоставлен больший приоритет над другими аналогично в Приоритетной очереди.

Во первых давайте реализуем приоритетную очередь с помощью модуля heapq предоставляемого самим Python

import heapq
q = []

heapq.heappush(q, (3, 'A')) #heappush is a method to add an 
heapq.heappush(q, (1, 'B')) #element
heapq.heappush(q, (2, 'C'))

while q:
   .heappop(q) #heappop is a method to
    print(next_item) #remove an element

Выход:

(1, 'B')
(2, 'C')
(3, 'A')

Возможно, вы сталкивались со многими вопросами, такими как min heap и max heap. Или, может быть, вы бы прочитали что-то вроде priority queue max size python и т. Д. Итак, вот ответ на все эти страшные вопросы. Здесь мы используем модуль/класс heapq в Python. Помните, что по умолчанию используется для минимальной кучи. Чтобы использовать его для максимальной кучи, умножьте каждый элемент на отрицательный 1, то есть -1

Демонстрация Макса кучи

#demonstartion of max heap using heapq in python 3
  
from heapq import heappop, heappush, heapify 
# An empty heap has been created
heap = [] 
heapify(heap) 


heappush(heap, -1 * 10) #adding elements using heappush
heappush(heap, -1 * 30) # function by multiplying them with
heappush(heap, -1 * 20) #-1
heappush(heap, -1 * 400) 

# printing the value of maximum element 
print("Head value of heap : "+str(-1 * heap[0])) 

  
# print all elements in the heap
print("The elements in heap: ") 

for i in heap: 
    print(-1 * i,) 
print("\n") (heap) 

  
# printing the elements of the heap 

print("The heap elements: ") 

for i in heap: 
    print(-1 * i,) 


#Result of above code after execution
#Head value of heap: 400
#The heap elements : 
#400 30 20 10 

#The heap elements : 
#30 10 20

Временная сложность кучи

Реализация heapq имеет O(log n) время для вставки и извлечения наименьшего элемента. Обратите внимание, что heapq имеет только реализацию кучи min, но есть способы использовать ее в качестве кучи max.

Реализация Приоритетной Очереди Через очередь.Класс PriorityQueue

Другой способ создания очереди приоритетов в Python 3-это класс PriorityQueue , предоставляемый Python 3. (вы также можете использовать его в Python 2, но, к сожалению, Python 2 больше не используется). А также приведенный ниже код может помочь вам перебирать приоритетную очередь в Python или (некоторые люди могут назвать это просто ) приоритетную очередь в структуре данных.

from queue import PriorityQueue
()

q.put((2, 'code'))
q.put((1, 'eat'))
q.put((3, 'sleep'))

while not q.empty():
   .get()
    print(next_item)

Выход:

(1, 'eat')
(2, 'code')
(3, 'sleep')

Временная Сложность С Использованием очереди.Класс PriorityQueue

Очередь <код>.PriorityQueue использует ту же реализацию heapq изнутри и, таким образом, имеет ту же временную сложность, что и O(log n) . Однако она отличается в двух ключевых аспектах. Во-первых, он синхронизирован, поэтому поддерживает параллельные процессы. Во-вторых, это интерфейс class вместо интерфейса function на основе heapq . Таким образом, очередь .PriorityQueue – это классический стиль реализации и использования очередей приоритетов в ООП.

Еще Один Не Очень Популярный Метод Приоритетной очереди

Существует множество методов или способов реализации очередей приоритетов в python. Один из не очень популярных методов-это href=”https://docs.python.org/3/tutorial/datastructures.html”>peek реализация, которая показана ниже. href=”https://docs.python.org/3/tutorial/datastructures.html”>peek реализация, которая показана ниже.

Peek реализация приоритетной очереди:

Что такое peek in Priority queue? Так что если вы используете java, то peek () – это просто еще один метод в очереди приоритетов, который дает вам 1-й элемент очереди приоритетов. Но в python 3, когда мы изучаем приоритетную очередь в Python 3, у нас нет встроенного метода, такого как peek(). Поэтому мы должны написать его реализацию.

Вот код для peek in Python priority queue (приведенный ниже код является исполняемым на Python 3.

import queue

class PeekablePriorityQueue(queue.PriorityQueue):
    def peek(self):
        """Peeks the first element of the queue
        
        Returns
        -------
        item : object
            First item in the queue
        
        Raises
        ------
        queue.Empty
            No items in the queue
        """
        try:
            with self.mutex:
                return self.queue[0]
        except IndexError:
            raise queue.Empty

В библиотеке python 3 доступно гораздо больше методов, модулей или классов, на которые вы можете ссылаться. И так много операций, которые вы можете выполнить в очереди приоритетов, таких как итерация по ней, уменьшение ключа, обновление значений и т. Д.

Заявки приоритетной очереди

Давайте рассмотрим приложения приоритетной очереди:

1. Очереди приоритетов используются в операционной системе для придания приоритета важной задаче над другой или просто обработки прерываний.
2. В светофоре, в зависимости от трафика, цветам будет отдан приоритет.
3. Реализация алгоритма Дейкстрычерез приоритетную очередь.
4. Мы можем сортировать кучи через приоритетные очереди.
5. Реализация алгоритма Prim может быть выполнена с использованием очередей приоритетов.

Надо Читать:

• Как преобразовать строку в нижний регистр в
• Как вычислить Квадратный корень
• Пользовательский ввод | Функция ввода () | Ввод с клавиатуры
• Лучшая книга для изучения Python в 2020 году

Вывод

В < strong>Python существует множество различных способов реализации очереди приоритетов . Два наиболее распространенных варианта создания приоритетной очереди-это использование модуля heapq или использование очереди .Класс PriorityQueue.

Если вы дошли до конца, то теперь вы являетесь экспертом по теме приоритетной очереди в структуре данных с помощью Python. Вы можете выполнять над ней все виды операций и использовать ее многие из вышеперечисленных приложений при решении задач. Не забудьте реализовать свои знания в Python 3, а не в других версиях, таких как Python 2.

Попробуйте реализовать программы на вашей стороне и дайте нам знать, если у вас есть какие-либо вопросы в разделе комментариев ниже.

Счастливого Пифонирования!