Min priority queue with constant time increase-key operation

1
votes

I've been searching for a while for a min-heap implementation variation that instead of offering amortised O(1) for decreasing a key, offers O(1) for increasing it. (With the trade off of having the decrease key operation with cost o(log(n)), since as here it's observed, both things are impossible at the same time).

I actually have a fixed size set of elements and I want to perform increments over the keys, or replacing the minimum element with a bigger one. So another approach that satisfies this would also be great!

Does anybody know a heap variation with constant amortised time increase-key operation?

Thanks!

2
algorithmheappriority-queue
I'm not sure there is such a variant. My suggestion is to implement a Paring heap, and profile it. Paring heap is simple to implement, and although its asymptotic behavior isn't quite as good as Fibonacci heap, in practice it usually performs better. If you can give us more information about your application, like the size and the typical mix of operations, we might be able to give you better advice. - Jim Mischel
Okay thanks! I'll consider it. I'm starting the project now so I still can't profile it, but I'll try this in a later stage. - Gonzalo Solera
And regarding my application, it's for an algorithm over a data stream, so I need to do this increase-key operation for every element. This is why I was looking for a constant time operation. The size of the heap will be a user specified parameter, which I still can't upper bound - Gonzalo Solera
I've been thinking that if an increase-key operation is executed over the minimum element, then the new minimum element needs to be found. And that's unlikely possible to do in constant time (For a similar reason why the remove-min operation is logarithmic in most heap implementations). So maybe I should try to find an implementation with constant time deletion and logarithmic insertion. Do you think that's possible? @Jim Mischel - Gonzalo Solera

2 Answers

2
votes

I think you're optimizing too soon. I recommend that you get your application up and running with a Pairing heap, and then profile it. There are just too many things you don't yet know about the data and how the heap structure will perform.

Binomial heap, Fibonacci heap, Pairing heap, and many other variants are rather difficult to analyze because their behavior depends very much on the mix of operations, the order of operations, and the nature of the data. In Pairing heap, for example, increase-key is O(1) if the node has no children. And whether the node has children depends on where the node is in the heap and how many times decrease-key or remove-first have been called.

I doubt you'll find a heap structure that has O(1) removal and logarithmic insertion. Even Brodal queue, which has O(1) for everything else, is O(log n) for removal. Note, however, that although Brodal queue is asymptotically optimum, it is, in the words of Brodal himself, "quite complicated" and "[not] practical in practice."

Get your program running. Profile it. Then decide whether you need a more performant priority queue structure.

1
votes

Actually the link you point to says that the three operations that you can't have together are O(1) for insert, find-min and increase-key. The decrease-key operation doesn't come into it. So one of the other operations would have to increase. I doubt that is possible.

But that said, a Fibonacci heap does offer amortized random O(1) key increase. Which is to say that for half the elements you don't need to move it. For a quarter you have to move it once. For 1/8 you have to move it twice, and so on. The worst case O(log(n)) is only paid if you increase the bottom element. So the average cost of increasing a random element is O(1).

You can even make the heap better than that. When you increase the value of an element, you can mark it as increased and make actually having it bubble up be lazy. Unless it reaches the bottom, you don't have to move it at all. So, depending on usage, most of the time you don't have to pay at all for moving things.