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.
这道题考察的是从超大规模数组中找出前 k 大元素，并要求保留重复值、按降序输出。基础解法可以用大小为 k 的最小堆，边遍历边维护候选集合；也可以用 Quickselect 先定位第 k 大附近的分界，再整理结果。进阶部分重点在并行化设计：如何把数组切分给多个 CPU 核心，如何合并各线程的局部 top-k，以及在存在大量重复值时如何让 Quickselect 的分区更稳定。比较时应关注时间复杂度、额外空间、核心利用率、同步开销、内存带宽瓶颈以及跨核心数据传输成本。一般来说，k 很小的时候最小堆更直接，n 很大且需要多核利用时，分段筛选再归并通常更实用。
