Jump to content
  • Advertisement

Archived

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

robinei

Searching a heap

This topic is 5365 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
Advertisement
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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!