3
$\begingroup$

Suppose we want to construct a queue with the following properties:

  1. 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.
  2. It must support deletion operations from any point in the queue
  3. It must support addition operations to any point in the queue
  4. 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.

$\endgroup$
4
  • 2
    $\begingroup$ Can you clarify a bit more what you mean by "the priority of each member must be known"? Does that mean that given a member we can easily extract its position in the queue, or does that mean that given a particular position we can access the member? Maybe both? $\endgroup$
    – nir shahar
    Jan 15 at 23:20
  • $\begingroup$ @nirshahar For each member, we must easily extract its position in the queue. We do not need to access a member by position. Thank you! $\endgroup$
    – Newb
    Jan 16 at 0:36
  • $\begingroup$ I still don't understand what is meant by "the priority of each member must be known". Do you mean that given a member, you want to find its priority in the queue? $\endgroup$
    – D.W.
    Jan 16 at 0:53
  • $\begingroup$ @D.W. that's what I meant, sorry about the confusion. I will edit my question. $\endgroup$
    – Newb
    Jan 16 at 1:16

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ As an added bonus, the "number of leaves under it" is sufficient information to balance the tree. en.wikipedia.org/wiki/Weight-balanced_tree $\endgroup$
    – Pseudonym
    Jan 16 at 2:19
  • 1
    $\begingroup$ @Pseudonym, oh, cool, I didn't know about that! Thank you for showing me that. $\endgroup$
    – D.W.
    Jan 16 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.