Given a very large array of n integers, find the k largest elements, including duplicates, in descending order.
First, solve it using a min heap and Quickselect.
Then optimize the solution for 2 CPU cores and eventually 128 cores.
Discuss how to split the workload, merge local top-k results, and handle duplicate values in Quickselect.
Compare parallel tree merging with parallel Quickselect, focusing on time and space complexity, CPU utilization, synchronization, memory bandwidth, and data transferred between cores.
Finally, identify the main bottlenecks and explain which approach performs better for different values of n and k.
This problem asks for the k largest elements in a very large array, including duplicates, in descending order. A standard solution uses a min heap of size k, while Quickselect can find the selection boundary in linear average time. The follow-up focuses on parallelization: splitting the array across cores, merging local top-k candidates, and handling duplicate-heavy partitions in Quickselect. A strong answer should compare parallel tree merging and parallel Quickselect by complexity, CPU utilization, synchronization overhead, memory bandwidth pressure, and inter-core data movement. In practice, heap-based approaches are simple and effective for small k, while parallel chunking plus merging can scale better on many cores for large n.
