Bottom K Selection
Bottom K Selection Bottom K Selection returns the $k$ smallest elements of an array. It is symmetric to Top K selection and can be implemented with heaps or partition based methods. The result may be unordered unless explicitly sorted. Problem Given an array $A$ of length $n$ and an integer $k$, return the $k$ smallest elements. Algorithm Heap Based Maintain a max heap of size $k$. bottom_k_heap(A, k): H =...