# Control of Priority Queue Order? And size limits on queues?

**URL:** <https://www.ruby-forum.com/t/control-of-priority-queue-order-and-size-limits-on-queues/176464>\
**Category:** Ruby\
**Created:** [September 30, 2009, 10:50pm UTC](https://www.ruby-forum.com/t/control-of-priority-queue-order-and-size-limits-on-queues/176464 "2009-09-30T22:50:59Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![masonkessinger](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/4da419/32.png) [@masonkessinger](https://www.ruby-forum.com/u/masonkessinger)\
**Post date:** [September 30, 2009, 10:50pm UTC](https://www.ruby-forum.com/t/control-of-priority-queue-order-and-size-limits-on-queues/176464/1 "2009-09-30T22:50:59Z")

</div>

I’ve successfully used the Priority Queue to sort ascending items for  
solving the 8-puzzle problem. I noticed that the Priority Queue method  
had  
a unique way of sorting items with matching keys. It puts the newest  
items  
furtherest from the top. The older a matching item is, the further it  
is  
towards the top. That is OK by me as it essentially added a negative  
g(n)  
node value to the h(n) heuristic value that aided in the A\* best-first  
algorithm. If the newest matching item had been added at the top, it  
would  
have slowed the program down by going down fruitless paths and  
probably would create a less optimal path to the results.

The code I used was: open\_queue = PQueue.new(proc{|x,y| x[0]\<y[0]}),  
where I  
was sorting on the first element of each item.

But for future use, is there a way to force the Priority Queue to always  
add  
the newest matching item in front of the older matching items? Please  
be  
aware I am not asking for a descending sort, which I know how to do.

Also, related to unsolvable problems, is there a limit to the size of  
the  
Priority Queue? Or, perhaps a better way to ask is what would limit the  
size of the Priority Queue. I would have to guess that the same limits  
would apply to any type of queue. I’ve noticed that searching the  
Priority  
Queue for a matching value item is very slow in Ruby. I had over 1300  
items  
in my Priority Queue by the time I killed the run as it had run all  
night to  
just get to that size. Yes, I realize this is an interpreted language.  
I’m  
just trying to push Ruby to its limits to see if it breaks.

Does anyone know?

No Sam

---

<div class="post-metadata">

**Author:** ![masonkessinger](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/4da419/32.png) [@masonkessinger](https://www.ruby-forum.com/u/masonkessinger)\
**Post date:** [October 2, 2009, 2:27am UTC](https://www.ruby-forum.com/t/control-of-priority-queue-order-and-size-limits-on-queues/176464/2 "2009-10-02T02:27:07Z")

</div>

On Wed, Sep 30, 2009 at 1:50 PM, Mason K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> But for future use, is there a way to force the Priority Queue to always add  
> the newest matching item in front of the older matching items?

Wouldn’t that stop being a priority queue and be a priority stack?

> I’ve noticed that searching the PriorityQueue for a matching value item is  
> very slow in Ruby.

A Priority Queue is not an ideal structure for searching, its designed  
for the use where you are going to be pulling stuff off in order of  
priority and, within priorities, order received.

If you want something that is optimized for searching for matches, you  
need a different structure; if you just need equality matching on the  
value (or part of a composite value), you can probably use a Ruby  
Hash, otherwise, you may need something special.

---

<div class="post-metadata">

**Author:** ![masonkessinger](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/4da419/32.png) [@masonkessinger](https://www.ruby-forum.com/u/masonkessinger)\
**Post date:** [October 2, 2009, 7:39am UTC](https://www.ruby-forum.com/t/control-of-priority-queue-order-and-size-limits-on-queues/176464/3 "2009-10-02T07:39:08Z")

</div>

Thanks for the reply Christopher.

No, it would still be a priority queue if I could control the order of  
MATCHING key values. I still want the unmatched key values to be sorted  
automatically in order ascending or descending as I push new entries  
onto  
the queue.

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.

I experimented with popping off the oldest matching entry and pushing it  
right back on to put it BEHIND the other matching entries, but it was so  
slow that it was a bad idea. Pushes onto Priority Queues is the slowest  
part of my code because of the automated sort.

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.

Reviewing the Enumeraable Class (mixed in with the Array Class) I  
noticed  
there is a sort\_by method that I might be able to use to have a major  
sort  
on the heuristic\_value (key) and minor sort on the node\_level. I’ll  
play  
with it. It could be expensive with time.

Does this make sense to you?

You are right about Priority Queues not being ideal for matching  
searches.  
It is painfully slow. Fortunately I only need a queue that is a few  
hundred  
entries at the most, although a queue with more than 100 entries can  
start  
to drag. I will explore other options in a future version of my first  
significant Ruby program that solves the 8-puzzle.

Regardless, I turned in my program today for the Advanced  
Artificial Intelligence class I’m taking and got credit for it.

Thanks for trying.

No Sam

---

<div class="post-metadata">

**Author:** ![masonkessinger](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/4da419/32.png) [@masonkessinger](https://www.ruby-forum.com/u/masonkessinger)\
**Post date:** [October 2, 2009, 6:52pm UTC](https://www.ruby-forum.com/t/control-of-priority-queue-order-and-size-limits-on-queues/176464/4 "2009-10-02T18:52:25Z")

</div>

On Thu, 01 Oct 2009 23:38:46 -0600, Mason K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> Thanks for the reply Christopher.
> 
> No, it would still be a priority queue if I could control the order of  
> MATCHING key values. I still want the unmatched key values to be sorted  
> automatically in order ascending or descending as I push new entries onto  
> the queue.

Your focusing on the definition of Priority, and ignoring the Queue part  
A queue is defined as a First-in-First-out (FiFo) data structure. In  
other  
words if I add ‘B’ to the Queue, then ‘A’, when I read from the Queue I  
get ‘B’  
then ‘A’.

A priority queue changes this behavior, in that items with the higher  
priority  
go first. Thus assuming ‘B1’ and ‘B2’ are considered equal priority, if  
I  
add  
‘B1’ to the Queue, then ‘B2’, when I read the Queue I MUST first get  
‘B1’  
then  
‘B2’ or it ceases to be a Queue.

A Stack on the other hand in a First-in-Last-out (FiLo) data structure.  
So  
if I  
add ‘B1’ then ‘B2’ and read the Stack, I get out ‘B2’ then ‘B1’ in that  
order.

Thus, what you are looking for is a Priority Stack, not a Priority  
Queue.

To answer your question, I don’t know of a pre-built Priority Stack for  
Ruby,  
but that doesn’t mean it doesn’t exist.

Hope this clears things up!

---

<div class="post-metadata">

**Author:** ![masonkessinger](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/4da419/32.png) [@masonkessinger](https://www.ruby-forum.com/u/masonkessinger)\
**Post date:** [October 2, 2009, 8:55am UTC](https://www.ruby-forum.com/t/control-of-priority-queue-order-and-size-limits-on-queues/176464/5 "2009-10-02T08:55:14Z")

</div>

On Fri, Oct 2, 2009 at 12:38 AM, Mason K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> 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.

> **[Heap (data structure)](https://en.wikipedia.org/wiki/Heap_%28data_structure%29)**
>
> In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: In a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node.
> The heap is one maximally efficient implementation of an abstract data type called a priority queue, and in fact, ...

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.

---

<div class="post-metadata">

**Author:** ![masonkessinger](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/4da419/32.png) [@masonkessinger](https://www.ruby-forum.com/u/masonkessinger)\
**Post date:** [October 2, 2009, 8:03pm UTC](https://www.ruby-forum.com/t/control-of-priority-queue-order-and-size-limits-on-queues/176464/6 "2009-10-02T20:03:51Z")

</div>

Mason,

On Wed, Sep 30, 2009 at 1:50 PM, Mason K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> The code I used was: open\_queue = PQueue.new(proc{|x,y| x[0]\<y[0]}), where  
> I  
> was sorting on the first element of each item.
> 
> But for future use, is there a way to force the Priority Queue to always  
> add  
> the newest matching item in front of the older matching items? Please be  
> aware I am not asking for a descending sort, which I know how to do.

You will need to change the matching process to be smart enough to  
handle  
what you want - fortunately it’s fairly easy to do with a couple of  
changes.  
You can do something along either of the following (gist here for easier  
reading - [Multi-Sort pqueue record · GitHub](http://gist.github.com/199934))

In essence we just create a class to hold your items that is aware of  
how  
you want to sort - you can either subclass  
an array if you want to keep that concept or dump the array and move  
your  
records to their own class.

require ‘pqueue’

pq = PQueue.new proc{|x, y| x.compare(y)}

#Do either the Array monkey\_patch or Record concept

class Array  
attr\_reader :insert\_time  
def compare(other\_record)  
#We want to return TRUE if this record should take  
#priority over the other record in the queue  
if self[0] == other\_record[0]  
insert\_time \> other\_record.insert\_time  
else  
self[0] \< other\_record[0]  
end  
end

def queue(pq)  
@insert\_time = Time.now()  
pq.push(self)  
end  
end

x = [1, 2, 3, 4]  
x.queue(pq)  
sleep 1  
y = [1, 2, 3, 4]  
y.queue(pq)

until pq.empty?  
itm = pq.pop  
p itm  
p itm.insert\_time  
end

class Record  
attr\_accessor :f1, :f2, :f3, :f4  
attr\_reader :insert\_time

def initialize(f1, f2, f3, f4)  
@f1, @f2, @f3, @f4 = f1, f2, f3, f4  
end

def compare(other\_record)  
#We want to return TRUE if this record should take  
#priority over the other record in the queue  
if f1 == other\_record.f1  
insert\_time \> other\_record.insert\_time  
else  
f1 \< other\_record.f1  
end  
end

def queue(pq)  
@insert\_time = Time.now()  
pq.push(self)  
end  
end

x = Record.new(1, 2, 3, 4)  
x.queue(pq)  
sleep 1  
y = Record.new(1, 5, 6, 7)  
y.queue(pq)

until pq.empty?  
p pq.pop  
end

John