[C++][Compute] Implement TopK/BottomK

[asfimport]

Heap-based topk can compute these indices in O(n log k) time

Reporter: Wes McKinney / @wesm
Assignee: Alexander Ocsa / @aocsa

Related issues:

• [C++] Resolve follow-up reviews for TopK/BottomK (is a parent of)
• [C++] Query engine umbrella issue (is a child of)
• [C++] Improve select_k_unstable performance (is related to)
• [R] Add Arrow methods slice_min(), slice_max() (is depended upon by)

PRs and other links:

• GitHub Pull Request #11019

_{Note: This issue was originally created as ARROW-1565. Please see the migration documentation for further details.}

[asfimport]

Antoine Pitrou / @pitrou:
Another possibility is to use quickselect.

[asfimport]

Wes McKinney / @wesm:
I reframed this issue as a query processing task. We need to be able to compute TopK/BottomK with chunked data

[asfimport]

Antoine Pitrou / @pitrou:
cc @bkietz

[asfimport]

David Li / @lidavidm:
Daniel Lemire compared various approaches (modifications of the heap approach or modifications of quickselect) and found that the heap wins in his tests: https://lemire.me/blog/2017/06/21/top-speed-for-top-k-queries/

If we want this to perfectly emulate Pandas's nlargest/nsmallest then there are some additional complications (inputs must have a defined order to resolve ties, and/or we must be able to track and output duplicate values).

[asfimport]

David Li / @lidavidm:
Issue resolved by pull request 11019
#11019