fireblade wrote: > I have implementation of A* using Binary heaps, and as usually > everything is good untill I need to update elemt in the middle > of the heap? > Anybody has a good algorithm of doing this efficiently/ > thanks > bobi
Sounds like you are looking for what some authors call an indexed heap: in addition to the binary heap array pq[], maintain another array qp[] so that qp[i] is the location in pq[] of element i. When you sift up or sift down, you need to update qp[] as well as pq[]. If the elements in the heap are objects instead of integers, use a hash table instead of the array qp[]. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
