patternMinor
Designing a Queue that efficiently tracks position
Viewed 0 times
efficientlydesigningpositiontracksthatqueue
Problem
Suppose we want to construct a queue with the following properties:
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.
- 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.
Solution
One simple data structure is a balanced binary tree, with members stored in the leaves, and augmented so that each internal node also stores the number of leaves under it. Now you can implement all of your operations in $O(\log n)$ time.
Operation 1 can be implemented by finding the leaf where the member $m$ resides (either add a pointer to the member struct to point to the leaf, or use a hash table to map from member to the appropriate leaf), then traverse parent pointers to get to the root; you can count the number of leaves to the left of $m$ by looking at the field in the nodes on the path from $m$ to the root, and their siblings.
To learn more, read about order statistic trees.
Conveniently, the extra information in each node is enough to ensure the tree remains balanced: see weight-balanced trees.
Operation 1 can be implemented by finding the leaf where the member $m$ resides (either add a pointer to the member struct to point to the leaf, or use a hash table to map from member to the appropriate leaf), then traverse parent pointers to get to the root; you can count the number of leaves to the left of $m$ by looking at the field in the nodes on the path from $m$ to the root, and their siblings.
To learn more, read about order statistic trees.
Conveniently, the extra information in each node is enough to ensure the tree remains balanced: see weight-balanced trees.
Context
StackExchange Computer Science Q#148431, answer score: 3
Revisions (0)
No revisions yet.