A star's priority queue.
Author
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.
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]
... 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]
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]
...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]
Author
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?
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?
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
