Does a binary heap support the decrease-key operation?

Question

According to http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variants, it takes Θ(logn) (which translates to O(logn)) to perform the decrease-key operation. However, there seems to be no site that includes a binary heap implementation with a decrease-key operation.

Given therefore the lack of implementations on the web, is it possible to perform the decrease-key operation in a binary heap?

[I implemented it in JavaScript](https://github.com/mhluska/Snakeception/blob/master/src/binaryheap.coffee). — Maros, Aug 27 '12 at 14:40
you may be interested in [Fibonacci heaps](https://en.wikipedia.org/wiki/Fibonacci_heap) which have `Θ(1)` `decrease-key` operations — Andre Holzner, Oct 30 '16 at 13:49

score 11 · Accepted Answer · answered May 06 '11 at 20:44

11

I figured this out:

In order to perform a decrease-key in O(logn), we have to know the location of the corresponding element in advance. A hash map and a good hash function can guarantee O(1) amortized time. After each modification, we have to update the hash map, which takes O(logn).
After determining the location of our element, we move our element up in case it has a greater priority than its parent (in a similar manner to insertion) or down if it has a lower priority than one of its children (in a similar manner to deletion) and update the modified elements' locations in the hash map.

answered May 06 '11 at 20:44

Alexandros

2

I think it's the other way around. The update of hash map takes O(1) while decrease-key takes O(lg(n)). – Wei Qiu Nov 03 '13 at 22:36
1

Update the hash map is O(log n) because you have to update it for every `swap( parent, child )` operation. There are O(log n) such operation in a `decreasekey` operation. – Mmmh mmh Oct 21 '14 at 14:19

1 Answers1