How to find kth largest element in (max) priority queue in O(m) time? Here is my exercise.


  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.


Can anyone elaborate on this maybe?

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." However, that did not help much.
You can implement FINDLARGEST recursively:

FINDLARGEST(k, vertex) # call with vertex = root
  if value(vertex) &lt; 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.