Stable priority queue

[Aaron W. LaFramboise]

Hello,

I understand that an easy way to make the standard std::priority_q ueue
stable is by including an integer stamp with each node that is
incremented each time a new node is pushed into the queue. However, no
matter what reasonably-sized type I use for the stamp, eventually the
stamp will 'wrap around' and possibly cause incorrect ordering of
elements. For my application, which queues elements very quickly and
runs for an indefinite amount of time, this scenario is a real concern,
and will eventually cause incorrect results.

Is there any easy and painless way of correcting this order-stamp
wraparound problem?
Aaron W. LaFramboise

[Siemel Naran]

"Kevin Goodsell" <us************ *********@never box.com> wrote in message

Siemel Naran wrote:

What is a stable priority queue?

I'm guessing items of the same priority come out in the order they were
inserted.

Then maybe we can use the protected member 'c'. The standard says

template <class T, class Container = std::vector<T>, ...>
class priority_queue {
protected:
Container c;
...
};

So we could derive our own class from priority_queue, and add read and write
functions that read directly into and out of 'c'. If deriving from a
non-polymorphic class bothers us, we can use private inheritance with using
declarations.

We could get stable queue's and stacks too.

Anyway, what is a priority_queue? Is it just like a queue, except that
items with the highest priority get retrieved by top() and pop() first? How
do they achieve O(lg(N)) for both push and pop (ie. how does the heap
work?).

[Dietmar Kuehl]

"Aaron W. LaFramboise" <aa********@c ox-internet.com> wrote:

I understand that an easy way to make the standard std::priority_q ueue
stable is by including an integer stamp with each node that is
incremented each time a new node is pushed into the queue. However, no
matter what reasonably-sized type I use for the stamp, eventually the
stamp will 'wrap around' and possibly cause incorrect ordering of
elements.
Use a 128-bit integer (eg. made out of four longs): I doubt that this one
will overflow on any currently available machine before the sun (note, not
the SUN) cheases to exist. Even if you account for faster processors you
should be on the safe side.
Is there any easy and painless way of correcting this order-stamp
wraparound problem?

It is hard to tell what you are really doing. If a O(log n) insert and
extract is all you need, in particular if you don't need to modify
priorities, a simple alternative is to use a map rather than a proper
priority queue: the map's key is the priority and the value is a queue
of items with the same priority. All you need to do is to provide a
suitable interface:

- empty() -> 'm.empty()'
- top() -> 'm.begin()->second.front() '
- pop() -> 'm.begin()->second.pop() ;
if (m.begin()->second.empty() ) m.erase(m.begin ())'
- push(e) -> 'm[e.priority].push(e)'

I don't think that any of the approach to priority queues is capable to
deal stability. At least, a vanilla implementation of all priority queues
I know (d-heap, priority queue, radix heap, splay heap) will not be stable.
I don't think that any of those heaps can be made inherently stable based
only on its operation, ie. you would always need some additional hack like
the sequence number.
--
<mailto:di***** ******@yahoo.co m> <http://www.dietmar-kuehl.de/>
<www.contendix. com> - Software Development & Consulting

[Dietmar Kuehl]

"Aaron W. LaFramboise" <aa********@c ox-internet.com> wrote:

I understand that an easy way to make the standard std::priority_q ueue
stable is by including an integer stamp with each node that is
incremented each time a new node is pushed into the queue. However, no
matter what reasonably-sized type I use for the stamp, eventually the
stamp will 'wrap around' and possibly cause incorrect ordering of
elements.
Use a 128-bit integer (eg. made out of four longs): I doubt that this one
will overflow on any currently available machine before the sun (note, not
the SUN) cheases to exist. Even if you account for faster processors you
should be on the safe side.
Is there any easy and painless way of correcting this order-stamp
wraparound problem?

It is hard to tell what you are really doing. If a O(log n) insert and
extract is all you need, in particular if you don't need to modify
priorities, a simple alternative is to use a map rather than a proper
priority queue: the map's key is the priority and the value is a queue
of items with the same priority. All you need to do is to provide a
suitable interface:

- empty() -> 'm.empty()'
- top() -> 'm.begin()->second.front() '
- pop() -> 'm.begin()->second.pop() ;
if (m.begin()->second.empty() ) m.erase(m.begin ())'
- push(e) -> 'm[e.priority].push(e)'

I don't think that any of the approach to priority queues is capable to
deal stability. At least, a vanilla implementation of all priority queues
I know (d-heap, priority queue, radix heap, splay heap) will not be stable.
I don't think that any of those heaps can be made inherently stable based
only on its operation, ie. you would always need some additional hack like
the sequence number.
--
<mailto:di***** ******@yahoo.co m> <http://www.dietmar-kuehl.de/>
<www.contendix. com> - Software Development & Consulting

[Claudio Puviani]

"Dietmar Kuehl" <di***********@ yahoo.com> wrote

Use a 128-bit integer (eg. made out of four longs): I
doubt that this one will overflow on any currently available
machine before the sun (note, not the SUN) cheases to exist.
Even if you account for faster processors you should be
on the safe side.

Gaa! Do people no longer do basic back-of-the envelope calculations?

If a 5GHz computer had an integer increment that took only one CPU cycle and
did NOTHING but increment a 64-bit int 5 billion times per second 24-hours a
day without interruption, it would take 117 _YEARS_ before you ran out of
numbers!!! If you throw in the obligatory jump to implement the loop and
made the jump also take a single CPU cycle, the duration leaps to a whopping
234 years.

The most generous thing I can say about using a 128-bit integer for this
purpose is that it's absurdly over-engineered. There's a lot worse that
could be said about the idea.

Claudio Puviani

[Claudio Puviani]

"Dietmar Kuehl" <di***********@ yahoo.com> wrote

Use a 128-bit integer (eg. made out of four longs): I
doubt that this one will overflow on any currently available
machine before the sun (note, not the SUN) cheases to exist.
Even if you account for faster processors you should be
on the safe side.

Gaa! Do people no longer do basic back-of-the envelope calculations?

If a 5GHz computer had an integer increment that took only one CPU cycle and
did NOTHING but increment a 64-bit int 5 billion times per second 24-hours a
day without interruption, it would take 117 _YEARS_ before you ran out of
numbers!!! If you throw in the obligatory jump to implement the loop and
made the jump also take a single CPU cycle, the duration leaps to a whopping
234 years.

The most generous thing I can say about using a 128-bit integer for this
purpose is that it's absurdly over-engineered. There's a lot worse that
could be said about the idea.

Claudio Puviani

[Howard]

"Claudio Puviani" <pu*****@hotmai l.com> wrote in message
news:0i******** *************@n ews4.srv.hcvlny .cv.net...

"Dietmar Kuehl" <di***********@ yahoo.com> wrote

Use a 128-bit integer (eg. made out of four longs): I
doubt that this one will overflow on any currently available
machine before the sun (note, not the SUN) cheases to exist.
Even if you account for faster processors you should be
on the safe side.
Gaa! Do people no longer do basic back-of-the envelope calculations?

If a 5GHz computer had an integer increment that took only one CPU cycle

and did NOTHING but increment a 64-bit int 5 billion times per second 24-hours a day without interruption, it would take 117 _YEARS_ before you ran out of
numbers!!! If you throw in the obligatory jump to implement the loop and
made the jump also take a single CPU cycle, the duration leaps to a whopping 234 years.

The most generous thing I can say about using a 128-bit integer for this
purpose is that it's absurdly over-engineered. There's a lot worse that
could be said about the idea.

Claudio Puviani

My envelopes must be old. They only support 32-bit math. :-)

-Howard

[Howard]

"Claudio Puviani" <pu*****@hotmai l.com> wrote in message
news:0i******** *************@n ews4.srv.hcvlny .cv.net...

"Dietmar Kuehl" <di***********@ yahoo.com> wrote

Use a 128-bit integer (eg. made out of four longs): I
doubt that this one will overflow on any currently available
machine before the sun (note, not the SUN) cheases to exist.
Even if you account for faster processors you should be
on the safe side.
Gaa! Do people no longer do basic back-of-the envelope calculations?

If a 5GHz computer had an integer increment that took only one CPU cycle

and did NOTHING but increment a 64-bit int 5 billion times per second 24-hours a day without interruption, it would take 117 _YEARS_ before you ran out of
numbers!!! If you throw in the obligatory jump to implement the loop and
made the jump also take a single CPU cycle, the duration leaps to a whopping 234 years.

The most generous thing I can say about using a 128-bit integer for this
purpose is that it's absurdly over-engineered. There's a lot worse that
could be said about the idea.

Claudio Puviani

My envelopes must be old. They only support 32-bit math. :-)

-Howard

[Dietmar Kuehl]

Siemel Naran wrote:

Then maybe we can use the protected member 'c'.
'std::priority_ queue' actually just uses 'std::make_heap ', etc. Anyway,
accessing the member directly is no good: the internal organization of
the heap essentially makes immediate stability without some tool
impossible.
Anyway, what is a priority_queue? Is it just like a queue, except that
items with the highest priority get retrieved by top() and pop() first?
This is the interface description: It has operations 'empty()', 'top()',
'pop()', and 'push()' like a 'std::stack' and what a 'std::queue' should
have, too (unfortunately, the latter uses 'front()' instead of 'top()').
However, the internal organization of the priority queue is a little bit
more involved.
How do they achieve O(lg(N)) for both push and pop (ie. how does the heap
work?).

The essential idea of several heap structure is to maintain the heap
property: the heap is viewed as a tree and each tree has its minimum
element in the root (reverse the comparison and it has the maximum
element in the root; this does not really matter as long as you stick
with one definition - I will use the minimum). In the container stored
in the 'std::priority_ queue' a binary tree is implicitly stored: the
element with index '0' is the root. The children of a node with index
'n' are the nodes with '2 * (n + 1) - 1' and '2 * (n + 1)'. The parent
of the node 'n' is the node '(n - 1) / 2' (I guess, I got the numbers
wrong somewhere; just draw a picture and number the nodes and things
should be relatively easy to work out). In any case, the tree is fully
balanced.

Inserting into a heap is pretty simple: you add a node to the lowest
level and exchange it with its parent if the parent has a bigger key.
This far, the representation of the tree does not at all matter and
other heaps, eg. a Fibonacci-heap, use a different structure than an
array to hold a heap although they also maintain the heap property.
Since the heap in the array is balanced, insertion takes at most
O(log n) steps.

Extracting from a heap, is also simple: you simply exchange the root
with the last element and bubble down the root again: check which of
the child nodes is the smaller one and exchange the node with this
child until the node is smaller than both children. This again takes
at most O(log n) steps.

This form of heap is called a "d-heap" in its general form where "d"
is the arity of the tree: the same approach works with non-binary
trees, too, although the computation of child and parent nodes changes
slightly. When I compared different priority queues, I found that
"d == 5" had the best performance for integer values stored in the
heap. An even bigger 'd' is probably better if the nodes itself become
bigger. Of course, this was based on a few tests with my own
implementation and probably does not hold up to a scientific analysis.

Other forms of priority queues provide additional capabilities, eg.
ability to change the key for the priority fast. Of some interest in
this direction are Fibonacci-heaps which can do changes of the keys
in such a form that it becomes amortized constant, at least when using
it for Dijkstra's algorithms for finding shortest paths (I don't
remember the details; it is possible that it is amortized constant in
general applications, too).
--
<mailto:di***** ******@yahoo.co m> <http://www.dietmar-kuehl.de/>
<http://www.contendix.c om> - Software Development & Consulting

[Dietmar Kuehl]

Siemel Naran wrote:

Then maybe we can use the protected member 'c'.
'std::priority_ queue' actually just uses 'std::make_heap ', etc. Anyway,
accessing the member directly is no good: the internal organization of
the heap essentially makes immediate stability without some tool
impossible.
Anyway, what is a priority_queue? Is it just like a queue, except that
items with the highest priority get retrieved by top() and pop() first?
This is the interface description: It has operations 'empty()', 'top()',
'pop()', and 'push()' like a 'std::stack' and what a 'std::queue' should
have, too (unfortunately, the latter uses 'front()' instead of 'top()').
However, the internal organization of the priority queue is a little bit
more involved.
How do they achieve O(lg(N)) for both push and pop (ie. how does the heap
work?).

The essential idea of several heap structure is to maintain the heap
property: the heap is viewed as a tree and each tree has its minimum
element in the root (reverse the comparison and it has the maximum
element in the root; this does not really matter as long as you stick
with one definition - I will use the minimum). In the container stored
in the 'std::priority_ queue' a binary tree is implicitly stored: the
element with index '0' is the root. The children of a node with index
'n' are the nodes with '2 * (n + 1) - 1' and '2 * (n + 1)'. The parent
of the node 'n' is the node '(n - 1) / 2' (I guess, I got the numbers
wrong somewhere; just draw a picture and number the nodes and things
should be relatively easy to work out). In any case, the tree is fully
balanced.

Inserting into a heap is pretty simple: you add a node to the lowest
level and exchange it with its parent if the parent has a bigger key.
This far, the representation of the tree does not at all matter and
other heaps, eg. a Fibonacci-heap, use a different structure than an
array to hold a heap although they also maintain the heap property.
Since the heap in the array is balanced, insertion takes at most
O(log n) steps.

Extracting from a heap, is also simple: you simply exchange the root
with the last element and bubble down the root again: check which of
the child nodes is the smaller one and exchange the node with this
child until the node is smaller than both children. This again takes
at most O(log n) steps.

This form of heap is called a "d-heap" in its general form where "d"
is the arity of the tree: the same approach works with non-binary
trees, too, although the computation of child and parent nodes changes
slightly. When I compared different priority queues, I found that
"d == 5" had the best performance for integer values stored in the
heap. An even bigger 'd' is probably better if the nodes itself become
bigger. Of course, this was based on a few tests with my own
implementation and probably does not hold up to a scientific analysis.

Other forms of priority queues provide additional capabilities, eg.
ability to change the key for the priority fast. Of some interest in
this direction are Fibonacci-heaps which can do changes of the keys
in such a form that it becomes amortized constant, at least when using
it for Dijkstra's algorithms for finding shortest paths (I don't
remember the details; it is possible that it is amortized constant in
general applications, too).
--
<mailto:di***** ******@yahoo.co m> <http://www.dietmar-kuehl.de/>
<http://www.contendix.c om> - Software Development & Consulting

[Dietmar Kuehl]

Claudio Puviani wrote:

"Dietmar Kuehl" <di***********@ yahoo.com> wrote

Use a 128-bit integer (eg. made out of four longs): I
doubt that this one will overflow on any currently available
machine before the sun (note, not the SUN) cheases to exist.
Even if you account for faster processors you should be
on the safe side.
Gaa! Do people no longer do basic back-of-the envelope calculations?

I had to study mathematics because I'm notoriously bad at
calculating things and mathematics is the only more or less
technical topic where you don't need to do calculations - you
only prove that they can be done. With 128-bit I'm definitely
on the safe side...
If a 5GHz computer had an integer increment that took only one CPU cycle
and did NOTHING but increment a 64-bit int 5 billion times per second
24-hours a day without interruption, it would take 117 _YEARS_ before you
ran out of numbers!!! If you throw in the obligatory jump to implement the
loop and made the jump also take a single CPU cycle, the duration leaps to
a whopping 234 years.
Well, this computation seems reasonable (even though I'm not fit
to verifying it). Actually, the OP mentioned that this approach
does not work for him and all I wanted to do in this area is to
show that it is just a question of how many bits you spend to
make the approach work.
The most generous thing I can say about using a 128-bit integer for this
purpose is that it's absurdly over-engineered. There's a lot worse that
could be said about the idea.

To me, the difference of using 128-bits or 64-bits is not really
there: yes, I need twice as much memory but who cares? The template
class for doing simple arithmetics does not care how many (unsigned)
longs it takes for its representation and there is no portable
64-bit integer. Over-engineered? I'd say I was too lazy to do a more
precise computation.
--
<mailto:di***** ******@yahoo.co m> <http://www.dietmar-kuehl.de/>
<http://www.contendix.c om> - Software Development & Consulting