3
У меня есть карта высот (2D-массив значений с плавающей запятой), и я хочу найти самую высокую точку на карте, как только я нашел эту точку, я хочу изменить ее значение, а значения всех близлежащих точек. Какая лучшая структура данных используется для эффективного поиска наивысшей точки?Лучшая структура данных для карты высот
Требования:
- Найти самую высокую точку эффективно
- Измените значение произвольного набора точек, этот набор всегда будет содержать самую высокую точку тока и нагрузки точек поблизости, дельта будет быть разными для каждой точки.
Мое текущее мышление - это очередь приоритетов, я могу найти наивысшую точку в O (1), и я могу изменить нагрузку значений и heapify в O (n log n).
Nb. Я отметил это как язык-агностик и Lua, потому что это скорее агностический вопрос языка, но я буду реализовывать окончательное решение в Lua.
хмм, это звучит как интересный способ сделать что-то. Написание очереди приоритетов в Lua должно быть весело: D – Martin
Это:) Я рекомендую сначала начать с версии на основе списка, а затем перейти к двоичной базе с кучей. Причина этого в том, что на основе списка намного быстрее реализовать, и, следовательно, вы знаете, был ли это правильный путь. Я рекомендую переопределить метаметоды сравнения объектов, чтобы в очереди приоритетов вы могли сравнивать их с операторами сравнения, поэтому очередь приоритетов может быть легко сделана общей. – ponzao
У меня уже была min-max-heap, реализованная на C#, поэтому я портировал это, это невероятно быстро: D – Martin