Я задавал вопрос на собеседовании по приоритетным очередям, и у меня есть простой вопрос, с которым я надеялся получить помощь. Вопрос в том:
Должны ли приоритеты быть интегральными? Могу ли я реализовать строковые приоритеты.
Заранее спасибо :-)
Приоритеты в очереди приоритетов
Ответы (1)
?
Приоритеты могут быть любыми, для которых определен частичный порядок, хотя общий порядок был бы более распространенным (например, целые числа или строки, упорядоченные лексиографически).
person
Antti Huima
schedule
02.11.2011
Вы уверены, что частичного заказа достаточно? Что оно не должно быть тотальным?
- person Jan Hudec; 09.01.2013
@JanHudec свойство кучи заключается в том, что объект в куче предшествует по порядку двум объектам под ним в куче; пока это свойство сохраняется все время, куча будет в порядке. Если вы столкнетесь с ситуацией, когда в куче находятся несопоставимые объекты один под другим, то куча больше не будет четко определена.
- person Antti Huima; 15.01.2013
Так что же гарантирует, что вы не получите два несопоставимых объекта друг под другом?
- person Jan Hudec; 15.01.2013
(Я почти уверен, что ничего. Все структуры кучи, обычно определяемые в учебниках, предполагают слабый общий порядок. Можно определить кучу для частично упорядоченных объектов, но я нигде этого не видел, и она не будет иметь такой хорошей сложности. )
- person Jan Hudec; 15.01.2013
Ничто не гарантирует этого. Куча, очевидно, обеспечивает линейный порядок, потому что объекты извлекаются из нее в определенном (линейном) порядке. Но можно было бы, например. представьте себе кучу, в которой, когда есть два несопоставимых брата и сестры, и один из них должен быть повышен (во время перколяции), можно было бы выбирать случайным образом. Я думаю, что куча по-прежнему будет работать логически правильно, т. е. никогда не будет извлекать сверху объект, которому предшествует любой другой объект в куче.
- person Antti Huima; 21.01.2013
Я подозреваю, что вы путаете частичное и слабое упорядочение. При слабом упорядочении несравнимые элементы образуют классы эквивалентности, и для этой цели вы можете рассматривать их как равные. Но частичное упорядочение может иметь элемент, несопоставимый с несколькими элементами, которые между собой сопоставимы, поэтому всякий раз, когда новый элемент входит в такую очередь, он должен сравниваться со всеми текущими минимальными элементами, чтобы найти, куда его поместить.
- person Jan Hudec; 21.01.2013
@JanHudec Я имел в виду частичный порядок, а не слабый порядок. Но я не думал об этом :D
- person Antti Huima; 29.01.2013
