1 //===-- Implementation of heap sort -----------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_LIBC_SRC_STDLIB_HEAP_SORT_H 10 #define LLVM_LIBC_SRC_STDLIB_HEAP_SORT_H 11 12 #include "src/__support/CPP/cstddef.h" 13 #include "src/stdlib/qsort_data.h" 14 15 namespace LIBC_NAMESPACE_DECL { 16 namespace internal { 17 18 // A simple in-place heapsort implementation. 19 // Follow the implementation in https://en.wikipedia.org/wiki/Heapsort. 20 21 template <typename A, typename F> 22 LIBC_INLINE void heap_sort(const A &array, const F &is_less) { 23 size_t end = array.len(); 24 size_t start = end / 2; 25 26 const auto left_child = [](size_t i) -> size_t { return 2 * i + 1; }; 27 28 while (end > 1) { 29 if (start > 0) { 30 // Select the next unheapified element to sift down. 31 --start; 32 } else { 33 // Extract the max element of the heap, moving a leaf to root to be sifted 34 // down. 35 --end; 36 array.swap(0, end); 37 } 38 39 // Sift start down the heap. 40 size_t root = start; 41 while (left_child(root) < end) { 42 size_t child = left_child(root); 43 // If there are two children, set child to the greater. 44 if ((child + 1 < end) && is_less(array.get(child), array.get(child + 1))) 45 ++child; 46 47 // If the root is less than the greater child 48 if (!is_less(array.get(root), array.get(child))) 49 break; 50 51 // Swap the root with the greater child and continue sifting down. 52 array.swap(root, child); 53 root = child; 54 } 55 } 56 } 57 58 } // namespace internal 59 } // namespace LIBC_NAMESPACE_DECL 60 61 #endif // LLVM_LIBC_SRC_STDLIB_HEAP_SORT_H 62