The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
a)Deletion of smallest element in heap

b)Insertion of an element in a heap will take

$O(n)$ or $O(logn)$ time?
asked in DS by Veteran (112k points) | 144 views
O(log n) only... We you have doubt mam
see in max heap for smallest element find , we need to search every element in leaf


And also when a heap tree created, we donot know, which leaf is empty. So, all leaves we need to search here too


then how log n?
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

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,576 questions
54,192 answers
71,147 users