The Gateway to Computer Science Excellence
0 votes

My question is in Question like find 5th Smallest element in a heap:

It requires O(logn) time if we do only Delete operation 5 Times.But what if the array contains no 5th smallest element say

our array contain [1,1,1,1,1,1,1,1,1,1]

now in this case we need to do extract min operation n number of times which would give nlogn time?

Plz Clear my doubt

in Algorithms by | 220 views

5th Smallest element in a heap is relative to the smallest element, hence in this case should return 1 i.e., the extract min should run 5 times and should return 1. But if u talk about the fifth smallest distinct element then implementing it through minheap is surely taking O(nlogn) for the array u mentioned. Instead u can first use one loop to check how many distinct numbers are there in an array which would take O(n) (by using concept similar to that in counting sort) and if there are less numbers, you can conclude that there is no distinct 5th smallest element. If more elements then u can continue with extract min.

I didn't get your question exactly. what do you want to ask?

To extract k-smallest element the time complexity is O(klogn), why?

I have considered the min-heap was already built[which takes O(n) time].
swap the root with the last node and fix the heap of heapsize-1(as we do not consider the last node to participate in heap fix), this will give next smallest element on root.
Similarly, repeat this process 2 time if you want 2nd minimum element and k-time if you want kth smallest element.
Each min-heap fix will take O(lgn) time and there are 'k' such min-heap fixes as we do min-heapfix after every min-extract.
I got sir but now i have a doubt which case to consider if question simply ask to find 7th smallest element now how to interpret it 7th distinct smallest element or simply 7th Smallest element.

Cuz for distinct it can be O(nlogn) and in Normal its O(logn)

Cuz for distinct it can be O(nlogn) and in Normal its O(logn)

 Can you show me how it is O(lgn)?

We can be given two Case:-

1. Using only standard heap operation :-

The reason is same as You commented above only the thing is O(klogn) = O(logn) cuz if we are finding 7th smallest element k = 7 which is O(7logn) = O(logn)

2. If Only traversal we have to do then its O(1) ?

1st smallest = will be at first level so 1 comparision

2st smallest = will be at level 1 or level 2 total 3 elements total comaparision in between 2^2 - 1 = 3

Likewise 7th element will be upto 7th Level so total number of comparisons = 2^7 - 1 =127

So O(1)

Please log in or register to answer this question.

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
52,315 questions
60,436 answers
95,248 users