Min Heap: A min heap is a data structure such that all nodes are less than or equal to its children, and the shape is a complete binary tree. An example of min heap is as follows:
Question #116: How much time will it take to insert a new element in the heap?
Options:
- O(n log (n))
- O(n)
- O(log(n))
- O(log (log(n))
Solution: We always want the heap to be a complete binary tree, hence we would insert it as the next element which would always keep the heap as complete. We would first insert the new element (let’s say “1”) as following:
Next, we would heapify this newly inserted element by moving this element upwards. Hence, after the next step, heap would look like as following:
In the worst case, it can move up till the root, which in this case will. The final heap after moving the newly inserted element at correct position would look like as follows:
Hence, in the worst case, the element would need to be moved log(n) steps, that is, the height of the heap. Hence, the correct answer is option 3.
Bytes of the day 