导言

堆排序是一种基于二叉堆数据结构的高效排序算法，具有 O (n log n) 的时间复杂度和原地排序的特性。使用模板实现堆排序可以使其灵活适用于各种数据类型，并支持自定义比较规则。

一、堆排序算法原理

堆排序主要分为两个阶段：

建堆阶段：将无序数组构建成一个二叉堆（最大堆或最小堆）
排序阶段：反复提取堆顶元素（最大值或最小值），并调整剩余元素维持堆特性

二叉堆是一种完全二叉树，对于最大堆，每个父节点的值大于或等于其子节点的值；对于最小堆，每个父节点的值小于或等于其子节点的值。

二、模板类实现

下面是完整的HeapSort模板类实现，基于提供的框架结构：

#include <vector>
#include <functional>
#include <iostream>
#include <algorithm>

// 模板类声明，默认使用std::less<T>作为比较器（构建最大堆）
template <typename T, typename Compare = std::less<T>> 
class HeapSort 
{ 
public:  
    // 构造函数：接收数组和大小，初始化容器和比较器
    HeapSort(T *arr, size_t size);  
    
    // 堆调整函数：维护堆的性质
    void heapAdjust(size_t parent, size_t heapSize);  
    
    // 排序函数：执行堆排序
    void sort();
    
    // 打印排序结果
    void print() const; 

private:  
    std::vector<T> _vec;  // 存储待排序元素的容器
    Compare _cmp;         // 比较器对象
};

// 构造函数实现
template <typename T, typename Compare>
HeapSort<T, Compare>::HeapSort(T *arr, size_t size) {
    if (arr && size > 0) {
        _vec.assign(arr, arr + size);
    }
}

// 堆调整函数：确保以parent为根的子树满足堆的性质
template <typename T, typename Compare>
void HeapSort<T, Compare>::heapAdjust(size_t parent, size_t heapSize) {
    size_t left = 2 * parent + 1;   // 左子节点索引
    size_t right = 2 * parent + 2;  // 右子节点索引
    size_t target = parent;         // 记录父节点和子节点中符合堆性质的节点索引
    
    // 比较左子节点与当前节点
    if (left < heapSize && _cmp(_vec[target], _vec[left])) {
        target = left;
    }
    
    // 比较右子节点与当前目标节点
    if (right < heapSize && _cmp(_vec[target], _vec[right])) {
        target = right;
    }
    
    // 如果目标节点不是父节点，则交换并继续调整
    if (target != parent) {
        std::swap(_vec[parent], _vec[target]);
        heapAdjust(target, heapSize);  // 递归调整受影响的子树
    }
}

// 排序函数：执行堆排序的主要逻辑
template <typename T, typename Compare>
void HeapSort<T, Compare>::sort() {
    size_t n = _vec.size();
    if (n <= 1) return;  // 空数组或单个元素无需排序
    
    // 1. 构建堆：从最后一个非叶子节点开始向上调整
    for (int i = n / 2 - 1; i >= 0; --i) {
        heapAdjust(i, n);
    }
    
    // 2. 排序阶段：逐个提取堆顶元素并调整堆
    for (size_t i = n - 1; i > 0; --i) {
        // 将当前堆顶元素（最大/最小）交换到数组末尾
        std::swap(_vec[0], _vec[i]);
        
        // 调整剩余元素为堆，堆大小减1
        heapAdjust(0, i);
    }
}

// 打印排序结果
template <typename T, typename Compare>
void HeapSort<T, Compare>::print() const {
    for (const auto& elem : _vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
}

三、使用示例

下面展示如何使用HeapSort类对不同数据类型进行排序，包括默认排序（升序）和自定义比较器（降序）：

#include "heap_sort.h"
#include <string>

// 测试整数排序
void test_int_sort() {
    std::cout << "=== 整数排序测试 ===" << std::endl;
    int arr[] = {5, 2, 9, 1, 5, 6};
    size_t size = sizeof(arr) / sizeof(arr[0]);
    
    // 默认使用std::less<T>，构建最大堆，最终得到升序结果
    HeapSort<int> heap_asc(arr, size);
    heap_asc.sort();
    std::cout << "升序排序结果: ";
    heap_asc.print();
    
    // 使用std::greater<T>，构建最小堆，最终得到降序结果
    HeapSort<int, std::greater<int>> heap_desc(arr, size);
    heap_desc.sort();
    std::cout << "降序排序结果: ";
    heap_desc.print();
    std::cout << std::endl;
}

// 测试浮点数排序
void test_double_sort() {
    std::cout << "=== 浮点数排序测试 ===" << std::endl;
    double arr[] = {3.14, 1.41, 2.71, 0.577, 1.618};
    size_t size = sizeof(arr) / sizeof(arr[0]);
    
    HeapSort<double> heap(arr, size);
    heap.sort();
    std::cout << "浮点数排序结果: ";
    heap.print();
    std::cout << std::endl;
}

// 定义一个结构体用于测试
struct Employee {
    std::string name;
    int salary;
    
    Employee(std::string n, int s) : name(std::move(n)), salary(s) {}
    
    // 为了打印方便，重载输出运算符
    friend std::ostream& operator<<(std::ostream& os, const Employee& e) {
        os << "{" << e.name << ", " << e.salary << "}";
        return os;
    }
};

// 测试结构体排序
void test_struct_sort() {
    std::cout << "=== 结构体排序测试 ===" << std::endl;
    Employee employees[] = {
        {"Alice", 5000},
        {"Bob", 3000},
        {"Charlie", 7000},
        {"David", 4000}
    };
    size_t size = sizeof(employees) / sizeof(employees[0]);
    
    // 自定义比较器：按工资比较
    auto cmp = [](const Employee& a, const Employee& b) {
        return a.salary < b.salary;
    };
    
    HeapSort<Employee, decltype(cmp)> heap(employees, size);
    heap.sort();
    std::cout << "按工资升序排序结果: ";
    heap.print();
}

int main() {
    test_int_sort();
    test_double_sort();
    test_struct_sort();
    return 0;
}

四、代码解析

4.1 模板参数说明

typename T：表示要排序的数据类型，可以是基本类型（int、double 等）或自定义类型
typename Compare = std::less：比较器类型，默认使用std::less，构建最大堆，最终得到升序结果

4.2 核心函数解析

构造函数：
- 接收原始数组和大小
- 使用 vector 存储元素，方便管理和随机访问
heapAdjust 函数：
- 功能：维护堆的性质，确保以指定节点为根的子树是一个有效的堆
- 实现：比较父节点与左右子节点，找到符合比较器规则的节点作为目标节点，必要时交换并递归调整
sort 函数：
- 建堆阶段：从最后一个非叶子节点开始向上调整，将整个数组构建成一个堆
- 排序阶段：反复将堆顶元素与当前堆的最后一个元素交换，然后调整剩余元素为新的堆

五、编译与运行

运行结果：

=== 整数排序测试 ===
升序排序结果: 1 2 5 5 6 9 
降序排序结果: 9 6 5 5 2 1 

=== 浮点数排序测试 ===
浮点数排序结果: 0.577 1.41 1.618 2.71 3.14 

=== 结构体排序测试 ===
按工资升序排序结果: {Bob, 3000} {David, 4000} {Alice, 5000} {Charlie, 7000}

六、性能分析

时间复杂度：
- 建堆阶段：O (n)
- 排序阶段：O (n log n)
- 总体时间复杂度：O (n log n)
空间复杂度：O (1)，堆排序是原地排序算法，仅需要常数级的额外空间
稳定性：堆排序是不稳定的排序算法，相等元素的相对位置可能改变

七、优缺点总结

优点：

时间复杂度稳定为 O (n log n)，不受输入数据分布影响
空间复杂度低，是原地排序算法
适合处理大量数据

缺点：

不稳定排序，不保留相等元素的相对顺序
缓存友好性较差，相比快速排序局部性更差
实际应用中通常比快速排序慢