Очереди с приоритетом, часть I: что это такое?

размещено по адресу:http://www.magdysul.com/blog/priority-queues-part-i-what-are-they/

Представьте, что у вас есть большой журнал финансовых транзакций, и вы хотите извлечь 5 крупнейших транзакций, которые произошли. У нас может быть несколько подходов к этому.

1. Сортировать их? Дух.

Если у нас есть 3 миллиона транзакций, скажем, в течение месяца. Нам нужно будет сделать следующее:

  • Храните все 3 миллиона транзакций в структуре данных (массиве?)
  • Сортировать массив
  • Вернуть последние 5 элементов (если это неубывающий порядок)

Но у нас есть фундаментальная проблема с этим подходом:

  • Слишком много элементов: мы будем использовать пространство, эквивалентное количеству элементов или больше, в зависимости от алгоритма сортировки.

2. Сравните каждую из 3 миллионов транзакций с массивом из 5 самых крупных транзакций, наблюдаемых на данный момент.

  • Вы можете подумать о том, чтобы быть более чутким по отношению к компьютерным ресурсам, если видите, что это хороший подход.
  • Временная сложность этого подхода будет O(N*M), где N — количество элементов, M — количество транзакций, которые мы хотим извлечь. Это громоздко, если M велико.

3. Приоритетные очереди

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

Очередь с приоритетом — это тип данных, который выполняет две основные операции: вставка и удаление максимума.

Приложения

Бывают ситуации, когда использование приоритетной очереди подходит просто идеально. Вот некоторые:

Но как формируется приоритетная очередь?

В следующей части мы рассмотрим реализацию приоритетных очередей.



Приоритетные очереди, часть II: Реализация
medium.com



использованная литература

  • Алгоритмы, 4-е изд.
  • Статьи в Википедии о кодировании Хаффмана, алгоритме Дейкстры, приоритетной очереди