Efficient nested priority queue

Question

I'm looking for a data-structure/algorithm (not multithreaded) which is essentially a nested priority queue. That is:

1. The next element to be taken is the one with the highest priority.
2. An element can either be a simple element with a priority, or it can be another priority queue (though a limit of one level of nesting is fine for my purposes). Regardless of the level of nesting, the element with the highest priority across the queue/sub-queues/sub-sub-queues/etc is the one chosen nexxt.
3. Elements can be added or deleted at any level, though a simple node never turns into a sub-queue (or vise-versa).
4. The priority of a simple element doesn't change after being inserted.

I haven't been able to come up with anything efficient/elegant, and Googling hasn't turned up anything.

Answer 1

I haven't actually built this, but I did some pretty extensive analysis on the idea and it seems like it should work. I call it a queue of queues. The reason I never built it is because the project I was building it for was canceled before I needed the queue.

First, I decided that a "simple element" would instead be a priority queue that contains a single element. Not having to manage two different types of elements simplified the design, and analysis showed that it shouldn't affect performance in any significant way.

Because a sub-queue's priority can change whenever a new item is added, or an item is removed from it, I elected to use a Pairing heap for the main queue and the subqueues. Pairing heap performs better than binary heap when you have to do a lot of priority changes. The problem with binary heap is that if you want to change an item's priority, you have to find the item first. In a binary heap, that's an O(n) operation. In pairing heap, the amortized cost of a priority change is O(log n) because you already have a reference to the node.

So the idea is, if you're adding a new sub-queue you just add it to the main queue and it'll get put in the proper place. If you're updating a sub-queue, you add or remove the item (which is O(log n) on the sub-queue), and then adjust the sub-queue's position in the main queue (which is O(log n) on the main queue).

All my analysis said that this should work quite well, although I'm still not sure how well it would work with multiple threads. I think I have a good idea how to synchronize access and not end up blocking the entire queue for every insertion and deletion, except for a very brief time. I guess I'll find out if I ever build it. It might be possible to create a lock-free concurrent pairing heap.

I selected Pairing heap because of its better performance in re-ordering keys, and also because it's much easier to implement than Fibonacci heap or many of the others, and although its asymptotic performance is slower than Fibonacci heap, its real-world performance is much, much better. The only drawback to me is that a Pairing heap will occupy more memory than an equivalent binary heap. It's the old time/space tradeoff.

Another option would be to implement a skip list priority queue, which also has O(log n) performance for insertion and changing priority. And I've seen lock-free concurrent skip list implementations. Implementing an efficient skip list isn't difficult in C, because it handles variable record sizes very well. In C# and other languages that don't allow you to build varying length structures, skip list can be a real memory hog.

As I said, I never actually built this thing, but all my research and design notes tell me that it should be reasonably easy to build and should perform quite well.