An ordered dictionary supporting decrease-key?

Question

Many fast priority queues (such as the Fibonacci heap and pairing heap) support a decrease-key operation, which takes an element already stored in the priority queue and efficiently decreases its priority. In the case of the Fibonacci and pairing heap, decrease-key can be performed faster than removing the element from the priority queue and later reinserting it.

I'm wondering if a similar operation can be supported on ordered dictionary structures (binary search trees, skiplists, etc.). Specifically, suppose that I have an ordered dictionary and want to change the key of some key/value pair to be a different key. Is it possible to do this in time O(1) or O(log log n) on any standard representation of an ordered dictionary? I'm curious because with a balanced BST this can be done in O(log n) time by removing the element and reinserting it, but it seems like there might be a faster way to do this.

Thanks!

Answer 1

Imagine the following scenario:

You start N elements. Now,

1. You create an "ordered dictionary" of size N containing N copies of the some value X that is larger than any element.
2. You then call decrease-key on each X, changing it to one of the N real elements.
3. Traverse the dictionary, reading off the elements in order.

In most implementations of ordered dictionaries, steps 1 and 3 would both take O(N) time. If decrease-key takes O(1) or O(log log N) time, then step 2 takes O(N) or O(N log log N) time. Which means that you could sort in O(N) or O(N log log N) time.

By the O(N log N) lower bound on comparison-based sorting, this means that you CANNOT do decrease-key in O(1) or O(N log log N) time unless either

• your ordered dictionary is NOT based on comparisons (which typically only happens if you know something special about the elements, such as they are all in the range 1-100), or
• your ordered dictionary does NOT support steps 1 and 3 in O(N) time (which would rule out all the usual suspects, such as BSTs or skip-lists).

Answer 2

A sorted array or sorted linked-list supports O(1) decrease- or increase-key (assuming no / minimal duplicates, see 4th paragraph). This is because, if you think about it, you'll need to at most swap 2 elements for the decrease- or increase-key operation.

Not the best data structures in practice (though they have their place), but still an answer.

The only constraint is that you need a pointer to the node to start with, because it will already take O(log n) and O(n) respectively just to find the node.

If there are duplicates, a move can take worst case O(n) for both (if most of the values are the same), which is pretty bad. However, for a linked-list, it should be possible to get O(1) by having some sort of linked-list of linked-lists, with each node in the large linked-list representing a specific value and each linked-list from there representing all nodes equalling that value.

My original answer as to why a BBST or skip-list won't work:

(didn't delete because it seems like a shame to go to waste)

Worst-case less than O(log n) for moving by a single element is not possible for a BBST or skip-list, though it will be at least as efficient as a re-insert, from what I can tell. Average case is likely less than O(log n).

We're searching for it - The look-up just to find the position of the element you want to move is O(log n) and obviously you'll need to do that.

If you already have the position for some strange reason:

Why worst-case move cannot be less than O(log n) in a BST: Consider when trying to move the root and the next element is at the height of the tree (e.g. the right child has a left child with a left child with a left child with a left child ... down to the height of the tree). You need O(log n) to find it.

Why worst-case move cannot be less than O(log n) in a skip-list: Consider a item that exists in O(log n) lists and is followed by an item that exists in O(log n) of those lists (if this is possible, it seems so from the picture, my understanding of skip-lists is somewhat basic). You will obviously be required to swap the applicable items in O(log n) lists.

If you already have the position, there can exist an efficient ordered structure for which it is possible, but probably not for any tree-based structure (because of the argument presented above), which are, to my knowledge, the majority of efficient ordered structures.