Question

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.

Answer 1

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.