Best datastructure for a heightmap

Question

I have a heightmap (a 2D array of floating point values) and I wish to find the highest point on the map, once I have found this point, I want to change its value, and the values of all nearby points. What's the best datastructure to use for efficient retrieval of the highest point?

Requirements:

• Find the highest point efficiently
• Change the value of an arbitrary set of points, this set will always contain the highest current point, and a load of points nearby, the delta will be different for each point.

My current thinking is a priority queue, I can find the highest point in O(1) and I can change a load of values and heapify in O(n log n).

Nb. I've marked this as language-agnostic and Lua, because it is a largely language agnostic question, but I will be implementing the final solution in Lua.

Answer 1

While you are building your priority queue I'd simply be scanning the array and returning the indices of the highest value found. I can then access any element of the array 'nearby' in O(1).

Or am I missing something ?

Answer 2

If memory is not that big of an issue I would store each value in a priority queue as a table so that each table has its data value and references to its closest neighbors. Something like this: { data = number, neighbors = { ... } }.