Top down heap construction when getting element one by one

Question

so I read that when you are getting elements one by one you should use bottom up heap constrcution rather than heapify which is top down, but What if i use the heapify algorithm every time i add a new element , basically doing the same from n/2 to 1 heapify(i) thing every time i add a element in array, what are the disadvantages in this approach as to using bittom up heap construction and what is the time complexity

Answer 1

The 'build-heap` method (what you call top-down building) is O(n). So every insertion into the heap would be an O(n) operation. Contrast that to inserting at the bottom and sifting up, which is O(log n) in the worst case, but closer to O(1) in practice. See Argument for O(1) average-case complexity of heap insertion.

If you really must insert into the heap immediately after receiving an item, then you don't really have a viable choice other than doing the standard insertion: add to the end of the heap and sift up.