I know there is an a scientific article out there which describes some complicated way of finding the kth smallest element in a min-heap in O(k), but this is for an introductory course on algorithms. I also read that doing a breath-first search might be a solution but i cant see how. Can anyone help?


i stumbled upon this on the wikipedia entry on min-max heap: "The structure can also be generalized to support other order-statistics operations efficiently, such as find-median, delete-median,[6]find(k) (determine the kth smallest value in the structure) and the operation delete(k) (delete the kth smallest value in the structure), for any fixed value (or set of values) of k. These last two operations can be implemented in constant and logarithmic time, respectively."

can anyone elaborate on this maybe?

  • $\begingroup$ There's a simple $O(k\log k)$ algorithm that runs extract-max $k$ times on the top $k$ levels of the heap (which are guaranteed to contain the $k$th largest element). $\endgroup$ – Yuval Filmus Feb 9 '18 at 23:23
  • $\begingroup$ Don't believe everything you read on the internet. $\endgroup$ – Yuval Filmus Feb 9 '18 at 23:29
  • $\begingroup$ yes i realize we can do it in O(klogk), but my assignment ask me to do it in O(k). if it helps i can cite the exact formulation of the question below: $\endgroup$ – sss Feb 9 '18 at 23:47
  • $\begingroup$ "FINDLARGEST(k): return the elements in the heap with key >=k"...."expand the priority queue (max-heap) so that it supports FINDLARGEST(k) in O(m) time, where m is the number of elements with key>=k" $\endgroup$ – sss Feb 9 '18 at 23:49
  • $\begingroup$ This is a different function. It returns all elements in the heap larger than a given key. You can easily code FINDLARGEST using "BFS" on the heap: start exploring the heap from the root going downwards, stopping at any vertex which is below $k$. In total you are exploring at most $3m$ nodes (each returned node, together with its two children). $\endgroup$ – Yuval Filmus Feb 10 '18 at 7:56

You can implement FINDLARGEST recursively:

FINDLARGEST(k, vertex) # call with vertex = root
  if value(vertex) < k: exit the function
  output vertex
  FINDLARGEST(k, left-child(vertex))
  FINDLARGEST(k, right-child(vertex))

If there are $m$ vertices whose value is at least $k$, then FINDLARGEST explores at most $3m$ vertices: each eligible vertex together with its two children.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.