Question

What is the running time to remove the maximum value and restore heap properties?

Answer 1

Ans : O(log n)

Explanation:

to remove max element from Heap takes O(1) time and To restore the heap It takes O(log n).

While restoring the heap we place last element of heap at the top and Go down the tree height while satisfying the condition of heap (parent node should be grater than its children node) .So we travel height of the heap while restoring the heap.

Total Running Time = O ((log n ) +1) =O(log n)     where n is number of elements in heap.  

NOTE: If you got any sort of help from this article please UPVOTE and in case of query do mention it in comments