Почему в приоритетных очередях в основном используется 0 как самый важный приоритет?

Question

Почему большинство очередей с приоритетом / кучей реализовано как 0 с наивысшим приоритетом? Я предполагаю, что упускаю какой-то ключевой математический принцип. Поскольку я недавно реализовывал свою собственную очередь приоритетов, казалось, что было проще написать функцию вставки, если приоритет вырос до целочисленного значения, но, очевидно, люди, умнее меня, думают, что это должно пойти другим путем.

Есть идеи?

Answer 1

Большинство приоритетных очередей реализовано в виде кучи Фибоначчи или чего-то подобного. Эта структура данных поддерживает извлечение минимума в постоянное время, что делает естественным присвоение нулю наивысшего приоритета и удаление элементов из очереди путем извлечения минимума.

Answer 2

Если оно когда-либо увеличивается, как вы можете установить что-либо на самый высокий приоритет? (+1 к ответу Россфаба:)

Answer 3

Причина, по которой это часто бывает иначе, заключается в том, что очереди приоритетов используются для реализации таких алгоритмов, как Dijkstra и A *, где приоритет - это расстояние до узла, и вы хотите сначала обработать более близкие узлы.

Answer 4

В качестве контрпримера, в том, что, безусловно, является одной из наиболее доступных (если не используется) реализаций очереди приоритетов, а именно STL std::priority_queue, элемент top() является численно самым высоким согласно operator<. Конечно, все привыкли к условию наименьшего порядка сортировки, стоящего перед очередью, поэтому это привлекает внимание многих людей при первом его использовании.

Answer 5

Не думаю, что для этого есть какая-то конструктивная причина. Вероятно, это просто потому, что большинство программистов привыкли думать о 0 как о первом элементе. Другая причина может быть в том, что перечислители начинаются с 0, поэтому первое определенное целочисленное значение перечисления будет равно 0.

Answer 6

В очереди с приоритетами нет ничего, что делало бы 0 лучшим выбором для наивысшего приоритета. Однако для того, чтобы написать многократно используемую реализацию, вам нужно будет что-то выбрать, и 0 хорошо определено, независимо от того, какой тип целочисленного значения или значения с плавающей запятой вы используете для своего приоритета.

Даже при написании частной реализации, если вы решите, что вам нужно только 256 уровней приоритета, и вы используете беззнаковый символ в качестве приоритета, а 255 - ваш главный приоритет, то вам придется внимательно просмотреть весь код, если вы решите вам нужно больше уровней.