## Book Notes

### 4.3 Heapsort: Fast Sorting via Data Structures

#### Where in the Heap?

Problem: Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap. Hint: you do not have to find the kth smallest element; you need only determine its relationship to x.

Solution: There are at least two different ideas that lead to correct but inefficient algorithms for this problem:

- Call extract-minktimes, and test whether all of these are less thanx. This explicitly sorts the firstkelements and so gives us more information than the desired answer, but it takes O(klogn) time to do so.
- The kth smallest element cannot be deeper than the kth level of the
heap, since the path from it to the root must go through elements
of decreasing value. Thus we can look at all the elements on the
first k levels of the heap, and count how many of them are less
thanx, stopping when we either find k of them or run out of
elements. This is correct, but takes O(min(n,2
^{k}-1)) time, since the top k elements have 2^{k}-1 elements.

An O(k) solution can look at only k elements smaller than x, plus at most O(k) elements greater than x. Consider the following recursive procedure, called at the root with i= 1 with count=k: