CODEWITHSUNDEEP
algorithmtime-complexitybinary-heap
RunOrVeith
RunOrVeith

Reputation: 4805

Check if x is bigger than k-th smallest number in a min-heap

I know this question was asked before. I read the following question: how to determine if the kth largest element of the heap is greater than x but I have further questions. I did not want to post in a thread that old. So:

Given a number x and a number k, check if x is bigger than the k-th smallest element in O(k).

The previous question does the same thing, but with max-heaps and smaller than. That is not the problem.

Consider a binary min-heap:

              1
      2               3
  12    17         50  90
23,18 80,88      51,52 91,92

Let x be 19 and k be 6.

The 6th smallest element is 18.

If I do the algorithm in the other thread, it would check as follows:

1+,2+,12+,23,18+,17+,80,88,3+

The + signals when the counter is increased.

How does the algorithm know that 18 is the k-th smallest number, not 3?

And why does the checking of 23, 80 and 88 not interfere with O(k)?

Upvotes: 4

Views: 2735

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55609

How does the algorithm know that 18 is the kth smallest number, not 3?

It doesn't matter to the algorithm - it simply counts the smaller numbers - it doesn't keep track of which one is the k-th smallest number.

If it finds more than k smaller numbers, it knows the k-th smallest number is smaller than x.

If we want to actually find the k-th smallest number, we'd likely need to do O(k log k) work, as we need to keep track of the candidates in order so we know which one is in the k-th position, or we could do an (expected) O(n) quickselect.

And why does the check of 13,80,88 not interfere with O(k)?

Think of it this way - each node only has 2 children, and we'll only process a node's children if it's smaller than x, so we can include 23 and 18 in 12's running time (we do a constant amount of work for 12, including the work involved for 23 and 18) and 17 in 2's running time.

Upvotes: 3

Related Questions