Archived

This topic is now archived and is closed to further replies.

Searching a heap

This topic is 5171 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m trying to implement A* and I''m thinking of using a binary heaps for the open and closed list. The problem is that I need to search them quickliy to check for nodes, but I can''t see an obvious way. Too bad they''re not ordered throughout the array... I could just pop them all to get them ordered, but it seems inefficient. Any ideas? Is there a better data structure for this purpose(that I can realistically hope to implement).

Share this post


Link to post
Share on other sites
I tried quickly reading the A* tutorial in the articles

For the open list it seems you do insert/remove, min, and find.
A balanced search tree or similar(Red-black, AA, biased, splay,2-4 etc) might be a good idea. All of these have O(log(n)) time per operation(splay is amortized though, meaning that m operations take O(mlog(n)) time, but no guarentee for a single operation). Except for min, asymptotically these are just as efficient as a heap, but a heap is much simpler, and has a smaller constant factor. If you like randomized structures, you can also use a "treap"

It seems that in the closed list you only do insert and find, so here i would use a hashtable.

[edited by - ziphnor on October 15, 2003 3:31:40 PM]

Share this post


Link to post
Share on other sites