So lets say we have a set of gps data points and your current location. If asked to give the closest point to your current location we can utilize a heap with the distance being the key. Now if we update the current location, I suspect that only a few of the keys will change enough to violate the heap property. Would it be more efficient to rebuild the heap after recalculating the keys or to run heapify (assuming that only a few of the keys have changed enough). It is assumed that we don't jump around with the new location (new current location is close to the last current location).
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
I'm pretty sure you can't (mis-)use heaps for your purpose. I suggest you use data structures that are specifically built for your problem instead.
If your set of GPS data points hardly ever changes, KD-trees are probably the best choice for this. If your data points are also moving around, then quad-trees are probably the best. If you're feeling particularly algorithmic, you could even try to employ locality-sensitive hashing.
If you don't want to query your data structure every time your current location changes, you could instead find the two closest points, compute the difference in the distances from you to the two points, and only re-query the data structure if your current location has moved away from its position when you queried the data structure than this difference.
So, if A and B are the two nearest points (A being the nearest) to the current position D, and you then start moving from D again and end up at position C, then you only have to query the structure again if |B-D| - |A-D| <= |C-D|, because only then have you moved away far enough from D to have a different point E become (potentially) interesting.
If your data points and current location can be really far away from each other, you may have to take the rounding of the earth into account. You probably don't have to, but don't forget about it.