CPU TopK算法
内容提要
TopK算法用于在未排序的数组中找到最大或最小的K个元素。常见的两种CPU TopK算法是O(N + KlogN)和O(N)算法。第一种算法使用堆构建和堆提取操作，时间复杂度为O(N + KlogN)。第二种算法使用中位数选择算法和线性扫描或分区算法，时间复杂度为O(N)。两种算法都可以在C++中实现。
延伸解读
堆构建TopK：有序输出的代价
堆构建TopK算法在提取K个元素时，由于堆性质，每次弹出的根节点是当前极值，因此得到的TopK元素天然有序。但TopK问题通常只要求找出元素，不要求排序，这种有序性成为额外开销，导致时间复杂度为O(N + K log N)，而非线性。若应用需要有序结果，此算法一举两得；若不需要，则可能浪费计算资源。
中位数选择TopK：线性时间但不保证有序
中位数选择TopK算法利用中位数选择算法找到第K个顺序统计量，再通过分区将数组分为TopK和剩余两部分，整体时间复杂度为O(N)，是真正的线性时间算法。但提取的TopK元素不保证有序，若需要有序输出，还需额外排序。该算法适合对时间效率要求高且不关心内部顺序的场景。
实现细节：索引获取与原地分区
堆构建算法中，若需获取TopK元素的原始索引，可使用pair存储值和索引，并自定义比较函数。中位数选择算法则直接对原数组分区，若数组可变，无需额外计算索引，分区后TopK元素位于数组一端。两种实现均依赖C++标准库函数，如std::make_heap、std::pop_heap和std::partition。
算法选择：根据需求权衡
选择哪种算法取决于具体需求：若K较小且需要有序结果，堆构建算法可能更合适；若追求线性时间且不要求有序，中位数选择算法更优。但中位数选择算法常数因子较大，实际性能可能受数据规模和实现影响。读者应根据应用场景和性能测试做出选择。
Q&A
CPU TopK算法有哪些常见实现？
常见的CPU TopK算法有两种：一种是基于堆构建的O(N + K log N)算法，另一种是基于中位数选择算法的O(N)算法。
堆构建TopK算法的时间复杂度是多少？
堆构建TopK算法的时间复杂度为O(N + K log N)，其中O(N)用于构建堆，O(K log N)用于提取K个元素。
中位数选择TopK算法为什么是线性时间？
中位数选择TopK算法使用O(N)的中位数选择算法找到第K个顺序统计量，然后通过O(N)的线性扫描或分区算法得到TopK元素，因此总时间复杂度为O(N)，是线性时间算法。
在C++中如何实现堆构建TopK算法？
在C++中，可以使用std::make_heap构建堆，然后使用std::pop_heap和vector的pop_back函数进行K次堆提取操作来获取TopK元素。
中位数选择TopK算法提取的元素是否有序？
中位数选择TopK算法提取的K个元素不一定有序，而堆构建TopK算法提取的元素是有序的。
中位数选择TopK算法在C++中如何实现？
中位数选择TopK算法的实现基于中位数选择算法，使用std::partition函数将数组分区，从而得到TopK元素。
