最适合高度图的数据结构

Question

我有一个高度图（一个浮点值的二维数组），我希望找到地图上最高的点，一旦找到这个点，我想改变它的值以及所有附近点的值。什么是最好的数据结构，以便有效地检索最高点？

要求：

- 高效地找到最高点 - 更改任意一组点的值，该集合将始终包含当前最高点和许多附近点，每个点的增量都不同。

我的当前想法是使用优先队列，我可以在O(1)时间内找到最高点，并且我可以在O(n log n)时间内更改大量值并进行堆排序。

注：我将此标记为与语言无关和Lua，因为这是一个基本上与语言无关的问题，但我将在Lua中实现最终解决方案。

- Martin

Answer 1

如果内存不是太大的问题，我建议将每个值作为表格存储在优先队列中，以便每个表格都具有其数据值和最近邻居的引用。类似于这样：{ 数据 = 数字，邻居 = { ... } }。

- ponzao

---

嗯，那听起来是一个有趣的做事方式。用Lua编写优先队列应该很有乐趣:D - Martin

我建议首先使用基于列表的版本，然后再转向基于二叉堆的版本。原因是基于列表的实现速度更快，因此您可以知道是否选择了正确的路径。我建议重写对象的比较元方法，以便在优先级队列中可以使用比较运算符进行比较，从而使优先级队列易于成为通用的。 - ponzao

我已经在C#中实现了一个最小-最大堆，所以我将其移植过来了，速度非常快 :D - Martin

很酷，我之前没有注意到你的消息 :) 解决方案达到了你想要的效果吗？ - ponzao

Answer 2

当你正在构建优先队列时，我只需扫描数组并返回找到的最高值的索引。然后，我可以在O(1)时间内访问“附近”的数组中的任何元素。

或者我错过了什么吗？

- High Performance Mark

---

扫描数组为什么只需要 O(1) 的时间复杂度呢？ :/ - Martin

我没有说扫描数组是O(1)。但是，如果给定数组元素的索引，则访问时间为O(1)。 - High Performance Mark

是的，但找到索引需要扫描整个数组，这正是我想避免的。 - Martin