62 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC_STDLIB_HEAP_SORT_H10#define LLVM_LIBC_SRC_STDLIB_HEAP_SORT_H11 12#include "src/__support/CPP/cstddef.h"13#include "src/stdlib/qsort_data.h"14 15namespace LIBC_NAMESPACE_DECL {16namespace internal {17 18// A simple in-place heapsort implementation.19// Follow the implementation in https://en.wikipedia.org/wiki/Heapsort.20 21template <typename A, typename F>22LIBC_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 sifted34 // 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 child48 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 internal59} // namespace LIBC_NAMESPACE_DECL60 61#endif // LLVM_LIBC_SRC_STDLIB_HEAP_SORT_H62