Heap data structure

Question

a)Deletion of smallest element in heap

b)Insertion of an element in a heap will take

$O(n)$ or $O(logn)$ time?

Comments

a) deletion of smallest element in min heap : O(1)

                                                     max heap : O(n)

b)insertion of an element into heap : O(logn)

---

For Min heap:

Deletion of smallest element -> Smallest element is found at the root so search time = O(1). Delete root will take O(logn) time to maintain the min heap property.

Insertion of smallest element -> At first element is inserted after the last leaf index. This element should occupy the root position eventually which would take time to climb up the tree. Hence time depends on height of tree so TC= O(logn).

For max heap:

Deletion of smallest element -> Smallest element must be present at one of the leaf positions. We need to scan through the entire last level. No. of leaves present in a tree with n nodes is approx n/2 so time taken to search for the smallest one is O(n) and to delete a leaf node it takes O(1) so total O(n).

Insertion of smallest element -> We can insert it after the last leaf node. It takes O(1). It needs no comparing with any other node because it is the smallest one and should be present in the last level.

Insertion of an element(not smallest or largest) in general takes O(logn).

 

 

 

---

@srestha mam, you didn't say it is min heap or max heap.... i assumed it as MIN HEAP

@MiNiPanda, gave clear explanation