Kth and closest points

Questions 1 to 5 of 8

1. 1. The kth largest value can be found with a heap of size k. Which heap should you keep, and why?

   A max-heap, because its top is the largest value and that is the answerA max-heap of size n, because it holds every value onceA min-heap of size k, because its top is the smallest of the k largest values kept so farA min-heap of size n, because sorting the heap gives the answer
2. 2. Two points are both at squared distance 4, and k = 1. The point (2, 0) is read first and (0, 2) second. Which point does kClosest keep, and why?

   (0, 2), because a tie always replaces the top(2, 0), because a new point replaces the top only when its distance is strictly smallerBoth points, because the heap grows when two distances are equal(2, 0), because the heap compares the x coordinates
3. 3. The lesson's large test reads 200,000 points for k = 5. The heap method costs about log2(k) steps for each point, as the lesson counts it. What is log2(5), rounded to two decimal places?

   Type a number.

4. 4. Which statements about the costs in this lesson are true? Choose all that apply.

   Pick every answer that is true.

   Sorting all n points costs O(n log n) stepsThe heap method costs O(n log k) steps and keeps about k points in memoryThe heap method is faster than sorting for every value of kQuickselect keeps only the k kept points in memory, so it uses less memory than the heap method
5. 5. What does this program print? ``cpp #include <functional> #include <iostream> #include <queue> #include <vector> int main() { std::priority_queue<int, std::vector<int>, std::greater<int>> heap; for (int x : {4, 1, 7, 3, 8, 5}) { heap.push(x); if (heap.size() > 3) { heap.pop(); } } std::cout << heap.top() << ' ' << heap.size() << '\n'; } ``

   7 35 68 35 3