You are given a min-heap containing n data items, along with a data item x and a positive integer k. Your task is to design an algorithm that runs in time O(k) and answers the following question: are there at least k items in the heap that are less than x?
Of course, you could go through the entire heap and just count the number of items that are less than x, but this would take time proportional to n. The challenge is to design an algorithm whose running time is O(k) by somehow using the heap property.