Re: Control of Priority Queue Order? And size limits on queues?

On Fri, Oct 2, 2009 at 12:38 AM, Mason Kelsey <[e-mail]> wrote:

>
> The way the Priority Queue works now is that if you push several entries
> into the queue, all with matching key values, say the same heuristic value
> in an A* best first search, the OLDEST (the one pushed in earliest) goes to
> the top and the NEWEST goes to the bottom of that group of matching key
> entries, that is, inserted AFTER the first entry with the same key value.
> For example, let's say you are pushing entries onto the PQueue that have
> key
> values lower than any other entries already on the PQueue and the PQueue is
> sorted in ascending order.  The several entries with matching lower key
> values all get sorted to the top of the queue.  What I'm wondering is if
> there is a way to change the Priority Queue so the LAST of the inserted
> matching entries goes in front of the others so that with the next pop you
> get the newest matching entry instead of the oldest?  I'm beginning to
> think
> that PQueue doesn't have that capability.
>
>
Wouldn't that make it out of order? If so, then it would no longer be a
priority queue. You could probably extend or wrap the code to handle this,
but you should really think about whether that is what you need. Perhaps add
another class which houses a priority queue and a regular queue, determines
which an item to be inserted belongs to, and when it is asked for the next
object, determines which to extract from.


> Since there is a sort method for array, perhaps I should just try using an
> ordinary array (of arrays) and sort the array after each entry is added.
> That must be what the PQueue is doing anyway.
>
>
Priority queues are usually implemented as heaps, which means insertion and
extraction takes O( lg n ) time, where as pushing then sorting would take O(
n lg n ), considerably worse. You could do a sorted insertion, which would
take O( n ), much better, but still nowhere near as good as the heap.

As a quick example, say you had 1024 elements, then inserting into a
priority queue takes a maximum of
lg(1024) = a10 + c steps
Moving all the elements down to make room for the one you are inserting in
an already sorted array takes
a1024 + c steps
And pushing onto the end, then resorting takes
1024 * lg(1024) = a1024 * b10 + c = ab10240 + c steps

Where a, b, and c are some constant value. Not necessarily the same constant
between the three different implementations, but the point is that the base
number of steps grows much much slower for the heap implementation, so as
the number of elements the priority queue houses grows very large, the heap
will be faster, even if it's a and c are much larger.

http://en.wikipedia.org/wiki/Heap_%28data_structure%29

If you are still using the code from
ftp://ftp.math.kobe-u.ac.jp/pub/knot/pqueue.rb
You can see that it does implement as a heap. You can view the array the
items are stored in by calling .qarray on your priority queue.

Also, you could possibly reduce the search time by writing your own search
method, which takes into account the structure of the priority queue.
Meaning you can rule out entire branches of the tree if the priority of that
branch's root is less than the priority of the element you are searching
for.