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).