Q7. Build Heap 2

[kartik.k.saxena]

Q) We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is:

Doubt: How is inserting n items into a heap an O(n) operation?

[mr.encoder (Encoder .)]

@kartik.k.saxena

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is:

An insert operation on a binary heap takes O(log⁡n) time, but an alternative approach we can use. which requires us to insert nn elements in heap without any computation i.e. in constant time. after which we can apply Heapify operation(this operation creates heap in linear time) on the array of those element and Hence obtain a Heap in O(n) time.