Suppose we want to construct a queue with the following properties:
- The priority of each member of the queue must be known. For example, for the head node, their priority is 1, for the next node, their priority is 2, etc. Then given a node, we must be able to determine its priority efficiently.
- It must support deletion operations from any point in the queue
- It must support addition operations to any point in the queue
- It must be possible to move a member of the queue up or down
We want an efficient design. Properties 2, 3, and 4 are trivially solved with a Doubly Linked List. But property 1 adds a significant challenge: now, every time an element is removed from or added to the middle of the list, all the other elements have to have their rank updated as well. The O(1) properties of a DLL are lost, and all the operations are now O(n).
Is there a way around this? Is there some other data structure that would allow me to compute the position of a member in the queue more efficiently?
My mind is going toward heaps or other tree-based data structures where it may be possible to know the sizes of subtrees so you can readily compute the rank of a given member of the queue. In reading around, this seems to come close to priority queues, but I'm not sure if a PQ describes accurately the properties I laid out above.