# Keyed queues with depth queries and delete

I'm interested in a data structure (let's call it a DMV queue, or DMV for short) over keys (say, strings) with the following operations:

• empty is a DMV containing no keys.
• enqueue(q,k) adds the key k to the back of the DMV q, unless k is already in q, in which case it does nothing.
• dequeue(q) deletes the key at the front of the DMV q, if one exists, and returns it.
• delete(q,k) removes the key k from the DMV q.
• depth(q,k) returns an natural number indicating the approximate number of keys between the key k and the front of the DMV q. Let $k_q$ denote the exact number of keys between k and the front of q. Then there must be some c such that for all k and q, $k_q/c$ < depth(q,k) < $ck_q$.

I think I know how to provide the queue operations in $\Theta(1)$ time and delete and depth in $\Theta(\lg n)$ time (all expected amortized). Is it possible to do better?

My proposed solution is as follows: Maintain a balanced tree with $O(1)$ operations at the ends. Nearly any finger tree will do. This tree will store the keys in queue order at its nodes. Also, annotate every non-spine node with its number of descendants.

Keep a hash table mapping keys to pointers to nodes in the tree.

To enqueue a key k, add k to the back of the tree. This invalidates $O(1)$ node pointers and creates $O(1)$ new node pointers, so we need only perform $O(1)$ hash table operations. Dequeue is similar.

To delete a key, we look it up in the hash table and find its location in the tree, then delete it from the tree. This takes $O(\lg n)$ time in the tree, and invalidates $O(\lg n)$ slots in the hash table. We must also maintain non-spine node size annotations in the tree, but this also only takes logarithmic time.

To find the depth of a key, we first annotate the spine nodes of the tree with their number of descendants. This takes $O(\lg n)$ time. We then look up the key in the hash table and find its location in the tree. We then follow parent pointers until we reach the root, summing the annotations at left siblings. Note that this is the exact depth.

Your solution can be modified to do everything in $O(1)$ amortized time. Instead of maintaining a balanced tree, just keep track of the number of successful enqueue operations (those in which something was actually added to the back of the queue) and attach that number to queue along with the item during a successful enqueue operation. To find the depth of a key, just take the difference between the number of successful enqueues when it was enqueued, and the number of successful enqueues when the item currently at the front of the queue was enqueued. Note that this gives exact depth.
• If you take n samples uniformly at random (with replacement) to estimate the proportion of items not deleted in a range, the variance is proportional to $1/n$. So you only need $O(1/\epsilon^2)$ samples to get any desired probability of getting within $\epsilon$ of the true proportion. This is only problematic if the true proportion is so small that $\epsilon$ is more than a factor of $c$. In this case, most of the items have been deleted. So if you get an estimate that's too low, the numbering is paid for by the previous deletions, giving constant amortized time. – Dave Jun 28 '11 at 8:47