Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 838
Alexandros Avatar asked May 05 '11 12:05

Alexandros


People also ask

What is decrease key in binary heap?

In this tutorial, we'll present a third operation called decrease-key, which allows us to decrease the value of a certain key inside the data structure. Mainly, the decrease-key operation is used in Dijkstra's algorithm when we discover a new path to a certain node at a lower cost.

What does a binary heap do?

Binary heaps are also commonly employed in the heapsort sorting algorithm, which is an in-place algorithm because binary heaps can be implemented as an implicit data structure, storing keys in an array and using their relative positions within that array to represent child–parent relationships.

Which statement about binary heap is false?

Statement (IV) is false, because construction of binary search tree from max-heap will take O(nlogn) time.

What does increase key do in heap?

Heap Increase Key Since we will want to use a heap to implement a priority queue, an operation of interest to us is the change key operation. In the case of a maximum priority queue the operation of interest is the increase key operation.


1 Answers

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.
like image 127
Alexandros Avatar answered Sep 20 '22 19:09

Alexandros