Letters from Readers
Reader Feedback: The C# Priority Queue
Readers share opinions about Priority Queues and the Surface tablet.
The Microsoft .NET Framework doesn't contain a priority queue class. Dr. James McCaffrey offered a C# implementation in his November article, "Priority Queues in C#". One reader wondered why items did not appear in an ordered manner:
I thoroughly enjoyed your article on priority queues, but there's one point that confuses me. In my opinion, a priority queue (PQ) should be ordered by default. In Figure 2, the item with priority 3 comes before the item with priority 2. The reason for this seems to be that when we're adding items, we compare them to their parents to determine if we need to switch them with their parents, but we don't compare them to their siblings. Of course, if we switch an item with its sibling, then we'll need to check the whole tree starting at the sibling node to ensure that we haven't created an inconsistency. There's also the possibility that there's an alternate way of traversing the binary heap. What's the best way of ensuring that when we traverse a PQ, we always obtain an ordered list?
Carlos
Atlanta, Ga.
Dr. McCaffrey responds:
It turns out that a priority queue is only partially ordered by definition, and so traversing a PQ won't generate data in order. The intent of a PQ is that only the very front node is "ordered," in a sense. The remaining nodes are not ordered. If you look closely at the screenshot in the article, you'll see that this is the case.
PQs are used in algorithms where only the one element with the highest priority is needed at any time. By not having to order the remaining nodes, PQs have better performance than binary trees. You're correct that a PQ could be implemented as a binary tree -- the root node would be the one with the highest priority, and all remaining nodes would, in fact, be ordered.
ARMed with Windows 8
Several readers questioned On VB columnist Joe Kunk about his reasoning in "Why I Pre-Ordered a Surface Tablet".:
So for $740, why not buy a laptop? Isn't that what you bought: a very low-end, 10-inch touchscreen laptop?
Paul
Iowa
Proprietary port and $40 for an adaptor ... that's [sliminess] of truly Apple proportions.
Dave Granger
United Kingdom
Joe Kunk responds:
The Surface is not a laptop replacement. I can't run Visual Studio or VMware on it. So my computing platform is a triad of Windows Phone, Surface tablet and Quad-Core i7 laptop. Each has its own important place in keeping me connected and productive.
Visual Studio Magazine wants to hear from you! Send us your thoughts about recent stories, technology updates or whatever's on your mind.
About the Author
This story was written or compiled based on feedback from the readers of Visual Studio Magazine.