Clever Geek Handbook

Algorithm to find the kth next element in an array

I couldn't solve the question, can you help?

For i=1 to i=n/2, if A[i]<=A[2i] and A[i]<=A[2i+1] A is called as a "bst"

What is the time complexity of finding the smallest element kth

in bst

with n elements?

+3


source to share


3 answers


I can do in O(klogk)

and out k<<n

- it will be pretty efficient compared to the alternatives.

The idea is to keep the heap as small as possible, start at the head (id == 0), which is the lowest element, and iteratively add all "new candidates" (which i

are "candidates" - 2i

and for a given current smallest 2i+1

).

Create a new empty mini-heap where each element contains tupple (x, i) - x is the key in the array and i is its index



set i = 0, currIdx = 0
heap.add((i,0))
while currIdx < k:
currIdx = currIdx + 1
   (x,i) = heap.popLowest()
   if i != 2i: //for i=2i=0, don't add it twice:
       heap.add((arr[2i],2i))
   heap.add((arr[2i+1],2i+1))
return heap.getTop()

Complexity of time O(klogk)

, each operation on the heap takes O(logN)

(where N

is the current size), and the heap grows to the maximum size N=k

, so all operations on the heap log(1) + log(2) + ... + log(k) = log((k)!)

, which is in O(klogk)

.

+1


source


There are two methods:



  • O (k ln (n)) time complexity.
  • O (k ln (k)) time complexity + O (K) space complexity.
+1


source


First, you mean "heap", not "bst" (the data structure you described is necessarily a heap, and not necessarily bst).

Secondly, it is not at all obvious that this problem is solvable in O (k) time - it was not until 1992 that Frederickson gave an O (k) -time algorithm for this . I still haven't read this article, but it's 18 pages of tricky technical argument, and I'm stunned that the Olympics organizers expected students to essentially come up with it from scratch! (Or maybe they expect they are already familiar with the algorithm - in which case I would say (a) it still asks quite a lot, and (b) this is not a very good question.)

+1


source






More articles:


All Articles