На этом шаге мы рассмотрим Использование этого класса для создания очередей с приоритетом.
Вы можете использовать сортированный список list, который позволяет быстро идентифицировать и удалять наименьший или наибольший элемент. Недостатком является то, что вставка новых элементов в список является медленной O(n) операцией.
Несмотря на то что точка вставки может быть найдена за O(log n) время с помощью алгоритма bisect.insort стандартной библиотеки, это решение всегда находится во власти медленного шага вставки.
См. документацию Python "bisect.insort": https://docs.python.org/3.6/library/bisect.html.
Поддержание упорядоченности путем добавления в конец списка и пересортировки также занимает минимум O(n log n) времени. Еще один недостаток - вам придется вручную заботиться о пересортировке списка во время вставки новых элементов. Пропустив этот шаг, можно легко внести ошибки, и ответственность за них всегда будет на вас как на разработчике.
Поэтому, на наш взгляд, сортированные списки подходят как очереди с приоритетом только в тех случаях, когда вставок немного.
>>> q = [] >>> q.append((2, 'программировать')) >>> q.append((1, 'есть')) >>> q.append((3, 'спать')) # ПРИМЕЧАНИЕ: Не забудьте выполнить пересортировку всякий раз, # когда добавляется новый элемент, либо используйте # bisect.insort(). >>> q.sort(reverse=True) >>> while q: next_item = q.pop() print(next_item) # Результат: (1, 'есть') (2, 'программировать') (3, 'спать')
На следующем шаге мы рассмотрим класс heapq.
