Dr. Damien's Development - Priority Queue

[DFGray]

Every once in awhile, you need something a bit off the beaten path.  I needed a priority queue awhile back and needed to write it in LabVIEW 7.0.  So I dusted off the nearest copy of Introduction to Algorithms by Cormen, Leiserson, and Rivest and implemented an iteration-based version of the algorithm.  The key things that make the algorithm relatively fast are:

1. Active management of the memory used by the queue
2. The queue operations are mostly done in-place (could be improved in LabVIEW 8.5+ with the In Place Element).

The queue was implemented as a standard array-based binary tree.  The data is a strict typedef with the priority as its first element.  The rest of the data can be anything.  Users of LabVIEW 8.2+ should consider using a LabVOOP object as the data to enable easier reuse.

I included a small example of finding the longest string in an array of strings (although there are much faster ways of doing that particular task).  The code is probably most useful in AI based applications (which is why I wrote it).  Have fun!

[AristosQueue (NI)]

There is a bug in Dr. Damien's implementation of the priority queue. When elements carry the same rank, the elements are being dequeued in the reverse order of enqueue order, which violates the FIFO nature of a queue. Attached is a VI that demonstrates the bug and a replacement for the one VI that needs a fix. The fix is easy -- there is a "Greater Than Or Equal" node that needs to be replaced with a "Greater Than" node.

These VIs are saved in LV 8.0.

I have now attached a second proof-of-bug VI. This one works as long as the bug exists, but breaks when the fix I offered earlier is applied. I am not sure at all what is going on here.

[Renée]

Aristos Queue,

It sounds like swapping the "Greater Than Or Equal" node with the "Greater Than" node was the correct fix for the issue that you described. When you do this, you say the VI breaks. What do you mean by breaks? Could this be due to the different LabVIEW version? Also, if the VI was created around the past implementation of the queue, changing that implementation might mean needing to change other items in the VI as well.

[Darin.K]

You need to add an explicit tie-breaker, for example the global insertion order (I would negate so you could use > on both values in a cluster).  Simply comparing the rank will not give proper ordering of the heap if you are expecting FIFO behavior.  The attempted fix of changing the comparison operator will work only in a very small number of special cases (as noted by AQ).

[AristosQueue (NI)]

Darin: That was the conclusion I was rapidly coming to. Adding a timestamp or sequence count to the cluster inside the heap seems harsh, but perhaps the only way. Basically, instead of Rank being a simple integer, Rank becomes a cluster of two integers, one that is passed in by the user and the other that is the internal sequence count. If you do some clever trickery to handle roll-over, you can make an essentially infinite sequence counter out of a uInt32... there's a couple places in the C++ of LV that we do that.

Any other ideas beyond that?

[Darin.K]

Any other ideas beyond that?

I think either the timestamp or counter provide a collision-free hash function to use with the heap.  With the TypeDefs in the original code it is very easy to add a I64 counter to the heap, and change the rank to a cluster of two elements.  You can get FIFO or LIFO by decrementing or incrementing the count with each insertion and storing that value with the rank (advantage over timestamp IMO).  Of course for playing around, the I64 is probably collision-free, but for production use it should probably be guaranteed by reclaiming values (rebuild the heap when counter reaches a certain value) and resetting the count if the heap is empty.  With these steps, a U32 or I32 could be substituted for the counter. 

I would probably not be using a simple heap if I wanted LIFO/FIFO behavior but would use a chained data structure instead (queues, native or home-built depending on LV version).  Perhaps DFGray was more interested in 'priority' than 'queue'. 

Which leads to my final thought:  How about some more built-in data structures like the queue, starting perhaps with trees.  Variant attributes are very nice, but only allow strings for keys and go through all of the work to build the tree but force you to do a O(N) operation (getting all of the keys and pulling the first element) to get the root which should be O(1).

[AristosQueue (NI)]

---

Darin.K wrote:

Which leads to my final thought:  How about some more built-in data structures like the queue, starting perhaps with trees.  Variant attributes are very nice, but only allow strings for keys and go through all of the work to build the tree but force you to do a O(N) operation (getting all of the keys and pulling the first element) to get the root which should be O(1).

---

That is a long and twisted tale, my friend, one whose telling I will not go into. Let me just say that I share your dreams, but dreams are often dashed against the rocks of reality. Maybe someday...

[Darin.K]

The year: 1992, I am playing with LV1 and my first thought upon dropping a loop is "What? No recursion, that is annoying." By LV4 I thought it was hopeless and stopped bugging people about. Maybe there is hope here after all.

[DFGray]

As has been speculated, I was only interested in "priority" and not "queue".  A more accurate description would perhaps be "priority heap".  It was developed for ranking routes in the wire routing algorithm of the codegen engine, and equivalent rankings meant I did not care which one was picked.  Being a pragmatic soul, if I needed LIFO or FIFO behavior, I would probably add a U64 to the ranking criterion.  I would also refactor so that the element itself is a LabVIEW object, removing the need to rewrite it or copy it for every data type.

My free time at the moment is pretty full.  Any takers?

[DFGray]

Another implementation option would be to change the element to an array or queue of elements. New elements with the same rank would be placed appropriately to give LIFO or FIFO performance.

This change could destroy performance, but would be a more intuitive data structure.