#doubt on heaps and binary search

Question

Consider the process of inserting an element into a max heap, where the max heap is represented by an array.Suppose we perform a binary search on the path from the new leaf to the root to find the position for newly inserted element, the number of comparisons performed is? # i m getting as O(logn) as upon applying binary search we wud compare O(logn) elements(neighbours and its own root only) plz clr my confusion

Answer 1

Yes, number of comparisons would be O(log n). But if you apply binary search, then there is no use of heap and actual insertion is much costlier, comparison O(log n) + O(n)shifting.

If you use heapify procedure you'll get O(log n) in total for insertion.

Comments

i didnt get ur point, actual insertion is much costlier in what?

and answer given is O(loglogn)

:(

---

it is costlier as after insertion you need to readjust the array which need O(n) time.

---

Even if we take Heap in the tree format, time to search will be O(n) only after applying Binary Search.

There is no ordering in heaps like BST, so if we want to search an element using BS we have to do multi-way binary search i.e. at each node we have to start BS in two directions and in worst case we will reach all leaf elements. So time complexity is O(n).

Answer 2

number of elements from  leaf to node =logn elements.

finding postion where node is to be inserted=loglogn(as for n elements binary search takes logn time).number of comparisons =loglogn.

now insert the element at position and call heapify(logn).  therfore total time loglogn+logn =O(logn).