| 101 | |
| 102 | template <typename Comparator> |
| 103 | void 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 | |
| 130 | template <typename InType, SortOrder sort_order> |
| 131 | void HeapSortNonNullsToOutput(std::span<uint64_t> non_null_input_range, |