All geek questions in one place

Best altitude data structure

I have a height map (a 2D array of floating point values), and I want to find the highest point on the map, as soon as I find this point, I want to change its value and the values ​​of all the nearest points. What is the best data structure used to efficiently find the highest point?

Requirements:

  • Find the highest point effectively
  • Change the value of an arbitrary set of points, this set will always contain the highest current point and the 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 the load of values ​​and heapify in O (n log n).

Nb. I marked this as an agnostic language and Lua, because it is rather an agnostic language issue, but I will implement the final solution in Lua.

+3
source share
2 answers

If the memory is not so large, I would save each value in the priority queue in the form of a table, so that each table has its own data and links to its closest neighbors. Something like this: {data = number, neighbors = {...}}.

+2
source

While you are creating a priority queue, I just scan the array and return the indexes with the highest value. Then I can access any element of the array "nearby" in O (1).

Or am I missing something?

0
source

Source: https://habr.com/ru/post/1734257/

More articles:


All Articles