На прошлой неделе я написал о своем первом набеге на двоичные кучи, который можно найти здесь. Знание кучи действительно полезно при изучении очередей с приоритетом, поскольку оптимальный (но не только) способ их реализации - это куча. В посте на прошлой неделе у меня также была ссылка на ответ, который я написал, показывающий, как создать максимальную кучу в JavaScript (здесь), а также некоторые важные методы для реализации. В том же ответе я добавил класс очереди с приоритетом.
Что такое очереди с приоритетом?
Очередь с приоритетом - это абстрактная структура данных. Это очень похоже на обычную очередь, за исключением того, что каждому узлу или элементу назначен приоритет в дополнение к его значению. Из очереди сначала удаляются узлы с наивысшим приоритетом. Если два элемента имеют одинаковый приоритет, тот из них, который был добавлен в очередь первым, будет удален первым.
Существует множество различных способов реализации приоритетных очередей. Мы могли бы использовать массив, связанный список или кучу. Двоичные кучи хорошо подходят для использования в качестве очередей с приоритетом, потому что максимальное количество кучи и минимальное количество кучи организованы на основе значения узла, которое меньше или больше, чем значение его родительского элемента, соответственно. Это означает, что большая часть логики для создания очереди с приоритетами уже существует в кучах. Поскольку кучи настолько просты в использовании для очередей с приоритетом, существует распространенное заблуждение, что очереди с приоритетом - это кучи. Хотя вам, вероятно, всегда следует использовать кучу для очереди с приоритетами, важно знать, что это не обязательно.
Почему не массив или связанный список?
Если бы мы использовали массив, временная сложность была бы намного больше. Самая большая слабость массива с точки зрения большого O - это переиндексирование. Например, если мы добавляем элемент в начало массива, каждый отдельный элемент после этого нужно переиндексировать. Добавление в конец намного эффективнее, но, к сожалению, это не решит наших проблем, так как очень скоро массив не будет иметь порядок приоритета. На этом этапе нам придется перебирать массив, чтобы определить, какой элемент имеет наивысший приоритет, что может занять очень много времени в зависимости от размера массива. Несмотря на то, что он справился бы со своей задачей, куча - гораздо более эффективный инструмент. Связанные списки имеют те же проблемы временной сложности, что и массивы для подобных задач.
Реальные приложения
Очереди приоритета используются нашими компьютерами все время, чтобы гарантировать, что наиболее важные операции выполняются в первую очередь. Они также используются при сжатии данных и алгоритме кратчайшего пути Джикстры. Однако концепция очереди с приоритетами не ограничивается информатикой. Внедрение вакцины против Covid-19 - отличный пример очереди с приоритетом. Вы можете думать о пожилых людях как о наивысшем приоритете, за ними следуют люди с подавленной иммунной системой, основные работники и так далее. Когда приоритет равен, например, два человека в возрасте от 90 лет, тот, кто первым позвонил или подал заявку на прием (или «встал в очередь»), будет первым, кто получит вакцину.
Веселая часть
Теперь, когда у вас есть хорошее представление о том, что такое очередь с приоритетом (или, насколько бы хороша эта идея у меня по крайней мере), вот код, который я использовал для реализации очереди с приоритетом! Я решил сделать Min Heap, так как на прошлой неделе я сделал Max Heap. Очередь с приоритетом может быть создана с помощью любого из них. При использовании минимальной кучи сначала удаляются узлы с наименьшим приоритетом. Хотя это может показаться нелогичным, на самом деле за пределами программирования «приоритет 1» довольно часто означает «наивысший приоритет». Это, конечно, можно сделать и с максимальной кучей, просто имейте в виду, что значение наивысшего приоритета будут удалены в первую очередь.
Во-первых, вот созданный мной класс узла. Эти узлы будут составлять нашу очередь приоритетов и относительно просты. Здесь нет указателей или чего-то подобного, только значение и приоритет этого значения.
Далее у нас есть наша очередь с основным приоритетом, без каких-либо методов.
Вот наш метод добавления нового узла в очередь.
И, наконец, вот метод удаления элемента с наивысшим приоритетом из очереди.
Спасибо за чтение, и я надеюсь, что вы нашли это полезным и информативным!
