Archived

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

GekkoCube

A star's priority queue.

Recommended Posts

GekkoCube    116
well, i dropped this question on my original thread in general programming, but the topic was kind of diverging...so ill ask it here. when implementing a priority queue with a min heap (for an A Star search algorithm), should i use an array-based heap or a pointer-based tree heap.? and is there any advantages either way? thanks alot.

Share this post


Link to post
Share on other sites
Fruny    1658
Well, you could use a std::deque-based std:: priority_queue... or you could use std::make_heap(), std:: push_heap(), std:: pop_heap().


... C++ already has priority queues and heap algorithms.


[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]



[edited by - Fruny on September 3, 2003 10:29:09 PM]

Share this post


Link to post
Share on other sites
Timkin    864
That's presuming that GekkoCube is writing in C++...

...on the assumption that this is not the case, or that GC wants to write his or her own heap...

I'd recommend a pointer-based heap over an array heap, since it's easier to deal with, requires less memory fiddling and is fairly easy to visualise on paper.

Timkin

[edited by - Timkin on September 4, 2003 10:55:48 AM]

Share this post


Link to post
Share on other sites
GekkoCube    116
Timkin,

thanks for your input.
i went ahead an implemented the min heap using a fixed size array. i have to admit, it''s not as obviousto conceptualize it just by looking at it first glance, as opposed to a binary tree that is pointer-based.

But managing it seems straight forward and rather simple really.
plus, i dont see how a pointer-based min heap requires less memory. in fact, if the array heap is no more larger than what i need, it should require less memory - shouldnt in?

Share this post


Link to post
Share on other sites
Timkin    864
quote:
Original post by GekkoCube i dont see how a pointer-based min heap requires less memory. in fact, if the array heap is no more larger than what i need, it should require less memory - shouldnt in?


An assumption on my part (sorry)... that you would be varying the size of the array when pushing or popping... which, of course, is not very sensible. Obviously, if you know the maximum size that your heap will be, just declare that memory when you initialise the heap and you''re fine from then on. Of course, if you''re really pushed for memory, dynamic resizing of arrays is computationally more costly than a pointer based heap.

Timkin

Share this post


Link to post
Share on other sites