MCPcopy Create free account
hub / github.com/apache/arrow / HeapSortNonNullsToOutput

Function HeapSortNonNullsToOutput

cpp/src/arrow/compute/kernels/vector_select_k.cc:103–128  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

101
102template <typename Comparator>
103void HeapSortNonNullsToOutput(std::span<uint64_t> non_null_input_range, Comparator cmp,
104 std::span<uint64_t> output_range) {
105 if (output_range.empty()) {
106 return;
107 }
108 std::span<uint64_t> heap = non_null_input_range.subspan(0, output_range.size());
109 std::make_heap(heap.begin(), heap.end(), cmp);
110
111 std::span<uint64_t> remaining_input = non_null_input_range.subspan(output_range.size());
112 for (uint64_t x_index : remaining_input) {
113 if (cmp(x_index, heap.front())) {
114 std::pop_heap(heap.begin(), heap.end(), cmp);
115 heap.back() = x_index;
116 std::push_heap(heap.begin(), heap.end(), cmp);
117 }
118 }
119
120 // fill output in reverse when destructing,
121 // as the "worst" (next-to-would-have-been-replaced) element is at heap-top
122 for (int64_t i = output_range.size(); i > 0; --i) {
123 output_range[i - 1] = heap.front(); // heap-top has the next element
124 std::pop_heap(heap.begin(), heap.end(), cmp);
125 // Decrease heap-size by one
126 heap = heap.first(heap.size() - 1);
127 }
128}
129
130template <typename InType, SortOrder sort_order>
131void HeapSortNonNullsToOutput(std::span<uint64_t> non_null_input_range,

Callers 1

DoMethod · 0.85

Calls 6

backMethod · 0.80
emptyMethod · 0.45
sizeMethod · 0.45
beginMethod · 0.45
endMethod · 0.45
GetViewMethod · 0.45

Tested by

no test coverage detected