Time taken in decreasing the node value in a binomial heap is

Category: QuestionsTime taken in decreasing the node value in a binomial heap is
Editor">Editor Staff asked 4 weeks ago

Time taken in decreasing the node value in a binomial heap is
 
(a) O(n)
 
(b) O(1)
 
(c) O(logn)
 
(d) O(nlogn)
 
I’m obligated to ask this question of Binomial and Fibonacci Heap in portion Heap of Data Structures & Algorithms I
 
The question was posed to me in exam.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Correct option is (c) O(logn)
 
Explanation: Decreasing a node value may result in violating the min property. As a result be there would be exchange in the value of parent and child which at max goes up to height of the heap.