CODEWITHSUNDEEP
data-structurespriority-queue
Alexandros
Alexandros

Reputation: 3064

Does a binary heap support the decrease-key operation?

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?

Upvotes: 17

Views: 5268

Answers (1)

Alexandros
Alexandros

Reputation: 3064

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.

Upvotes: 12

Related Questions