Heap sorting algorithm implemented by C++.

heap_sort.cpp

/*
 * @author  duruyao
 * @file    heap_sort.cpp
 * @desc    
 * @date    2021-10-02
 * @version 1.0
 */

#include <vector>
#include <iostream>

template<typename T>
void keepHeap(std::vector<T> &input, int begin, int end, int (*cmpFunc)(const T &, const T &)) {
    auto max = begin, left = 2 * begin + 1, right = 2 * begin + 2;
    if (left < end && cmpFunc(input[left], input[max]) > 0) {
        max = left;
    }
    if (right < end && cmpFunc(input[right], input[max]) > 0) {
        max = right;
    }
    if (max != begin) {
        std::swap(input[begin], input[max]);
        keepHeap(input, max, end, cmpFunc);
    }
}

template<typename T>
void buildHeap(std::vector<T> &input, int begin, int end, int (*cmpFunc)(const T &, const T &)) {
    for (int i = end / 2 - 1; i >= begin; i--) {
        keepHeap(input, i, end, cmpFunc);
    }
}

/**
 * heapSort sorts data set by heap sorting algorithm.
 *
 * ---time complexity---
 *
 * best    case:    O(n * log n)
 * average case:    O(n * log n)
 * worst   case:    O(n * log n)
 *
 * ---when to use---
 *
 * (1) algorithm is required to perform well under the worst case.
 *
 * ---parameters and return---
 *
 * @tparam T        is a certain data type
 * @param input     is a data set to be sorted
 * @param begin     is the first index
 * @param end       is the index past the last index
 * @param cmpFunc   is a function for comparing elements of data set
 */
template<typename T>
void heapSort(std::vector<T> &input, int begin, int end, int (*cmpFunc)(const T &, const T &)) {
    buildHeap(input, begin, end, cmpFunc);
    for (int i = end - 1; i > begin; i--) {
        std::swap(input[begin], input[i]);
        keepHeap(input, begin, i, cmpFunc);
    }
}

int cmpInt(const int &n1, const int &n2) {
    return n1 - n2;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &input) {
    for (auto &it : input) { os << it << " "; }
    return os;
}

int main(int argc, char **argv) {
    std::vector<int> array;
    for (int i = 0; i < 40; array.push_back(random() % 100), i++);
    std::cout << array << std::endl;
    heapSort(array, 0, (int) array.size(), cmpInt);
    std::cout << array << std::endl;
    return 0;
}