Archived

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

robinei

Searching a heap

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
Any node in the heap is greater than all it''s children nodes, right?

Maybe it would be an idea to search it recursively, kind of like a quad tree or something like it?

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