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.