8

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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • don't think so. in every ordered structure i know, finding time is O(log n). and always you have to find element after which your decresed key should be placed – piotrek Jan 05 '13 at 22:32
  • @piotrek- Typically, to implement decrease-key, you store external pointers into the structure so that you can access the element whose key should be decreased in time O(1). That time is generally not counted in the decrease-key time. – templatetypedef Jan 05 '13 at 22:34
  • yes, but in ordered collection you have to find another key - they one after which you will place the key you are just decreasing. in queues you don't have to find such key – piotrek Jan 05 '13 at 22:35
  • @piotrek- In queues you still do have to do some lookups to figure out where to place things. For example, the pairing heap will merge the appropriate subtree back into the master tree, so it will have to do some work to figure out where it goes. – templatetypedef Jan 05 '13 at 22:37
  • @templatetypedef Where would you store these external pointers? Won't this also be in some sorted structure that requires you to do a lookup? – Bernhard Barker Jan 05 '13 at 22:52
  • @Dukeling- You could imagine that I have an array of these pointers where I process the elements in the array in some order, calling decrease-key on each. In that case, I do only O(1) work finding the pointer. Alternatively, think of Dijkstra's algorithm, where you might embed the pointers in the objects themselves so that as you follow edges in the graph, you can immediately follow the pointers out of the nodes and into the priority queue. – templatetypedef Jan 05 '13 at 22:55

2 Answers2

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).
Chris Okasaki
  • 4,875
  • 1
  • 20
  • 19
0

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.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
  • 1
    @Dukeling- You don't necessarily need to do O(log n) work to find the element that's going to have its key decreased; see the discussion in the comments. Also, what you've shown here is that using a normal BST/skiplist that it won't work, not that there is no way to accomplish this using a more complex structure. – templatetypedef Jan 05 '13 at 23:24
  • @templatetypedef Edited to technically answer the question, though I doubt this is the answer your looking for. – Bernhard Barker Jan 05 '13 at 23:49
  • You're not answering the question whether it can be done, but whether a standard implementation of a BST will do it. – blubb Apr 17 '13 at 19:08
  • @blubb Edited to make my answer a little more clear (and elaborated a bit). – Bernhard Barker Apr 22 '13 at 10:44