一、项目背景详细介绍

堆排序（Heap Sort）是一种基于完全二叉树的比较排序算法，时间复杂度为 O(n log n)。其核心思想是先将待排序数组构建成一个“堆”——一种满足父节点与子节点之间有序关系的完全二叉树——然后反复取出堆顶元素放入数组末尾并调整堆，直至排序完成。

根据有序关系的不同，堆可分为：

• 大顶堆（Max‑Heap）：父节点值 ≥ 子节点值，堆顶为最大值。

• 小顶堆（Min‑Heap）：父节点值 ≤ 子节点值，堆顶为最小值。

在实际开发中，大顶堆常用于实现升序排序（每次取出最大值放至末尾），而小顶堆可用于实现降序排序或优先队列。掌握堆的构建与调整逻辑，不仅能加深对树形结构与索引映射的理解，也有助于开发优先队列、实时数据流 top‑k 问题等场景。

---

二、项目需求详细介绍

本项目旨在使用 Java 语言实现堆排序的两种变体，并封装成通用工具，功能需求包括：

1. 构建大顶堆

   • 提供方法 void buildMaxHeap(int[] arr)，原地将数组构建为大顶堆；

2. 大顶堆排序

   • 提供方法 void heapSortAsc(int[] arr)，利用大顶堆实现升序排序；

3. 构建小顶堆

   • 提供方法 void buildMinHeap(int[] arr)，原地将数组构建为小顶堆；

4. 小顶堆排序

   • 提供方法 void heapSortDesc(int[] arr)，利用小顶堆实现降序排序；

5. 堆的动态增删

   • 提供方法 void heapInsert(int[] heap, int value) 与 int heapExtract(int[] heap)，支持向堆中插入新元素与弹出堆顶（可结合可变长度数组或 List<Integer> 实现）；

6. 命令行工具模式

   • 提供 Main 类，支持参数：

     • --mode <asc|desc>：选择升序或降序；

     • --values <v1,v2,…>：输入待排序的整数列表；

7. 单元测试覆盖

   • 使用 JUnit 5 对核心方法编写测试，验证各种边界（空数组、单元素、重复元素）与正常排序结果；

8. 性能与稳定性

   • 原地排序，无额外数组；

   • 支持大规模数据（百万级）堆构建与排序，确保无栈溢出或性能退化；

---

三、相关技术详细介绍

为满足项目需求，将使用以下技术与概念：

1. Java 核心

   • 原生数组操作、索引换算（父节点 i 的左子节点索引 2*i+1、右子节点 2*i+2）；

   • 递归与迭代实现堆调整（heapify）方法。

2. 命令行解析

   • Apache Commons CLI：定义并解析 --mode 与 --values 选项，输出排序结果；

3. 单元测试

   • JUnit 5：测试堆构建、排序、插入、弹出等所有方法的正确性；

4. 性能测试

   • 如需，可使用 JMH 对上百万数据排序进行基准测试，验证 O(n log n) 性能。

---

四、实现思路详细介绍

1. 通用工具类 HeapSortUtil

   • 私有构造，所有方法为静态；

   • 包含 swap(int[] arr, int i, int j) 辅助方法。

2. 大顶堆

   • heapifyMax(int[] arr, int heapSize, int root)：
     以 root 为根节点，调整三者（根、左、右）使得子树成为大顶堆；

   • buildMaxHeap(int[] arr)：
     从最后一个非叶子节点 (n/2−1) 向下依次调用 heapifyMax；

   • heapSortAsc(int[] arr)：
     先 buildMaxHeap，然后从末尾开始交换 arr[0] 与 arr[i]，缩小 heapSize 并重新 heapifyMax，直至排序完成。

3. 小顶堆

   • heapifyMin(int[] arr, int heapSize, int root)：
     类似 heapifyMax，但保证父节点为三者中最小；

   • buildMinHeap(int[] arr) 与 heapSortDesc(int[] arr)：
     同理，只是调整方向相反。

4. 动态堆操作

   • heapInsert：
     将新值加在数组末尾，向上“浮”调整：与父节点比较并交换，直至父节点有序；

   • heapExtract：
     取堆顶（最大或最小），将末尾元素放入根并缩减大小，调用对应 heapify 使堆恢复。

5. 命令行入口 Main

   • 解析 --mode 和 --values，将输入字符串拆分为 int[]；

   • 根据模式调用 heapSortAsc 或 heapSortDesc 并打印排序结果。

五、完整实现代码

// 文件：pom.xml
/*
  Maven 项目对象模型，管理依赖与构建
*/
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 
                             http://maven.apache.org/xsd/maven-4.0.0.xsd">
  <modelVersion>4.0.0</modelVersion>
  <groupId>com.example</groupId>
  <artifactId>heap-sort-demo</artifactId>
  <version>1.0.0</version>
  <properties>
    <maven.compiler.source>1.8</maven.compiler.source>
    <maven.compiler.target>1.8</maven.compiler.target>
    <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
  </properties>
  <dependencies>
    <!-- Commons CLI 用于命令行解析 -->
    <dependency>
      <groupId>commons-cli</groupId>
      <artifactId>commons-cli</artifactId>
      <version>1.4</version>
    </dependency>
    <!-- JUnit 5 用于单元测试 -->
    <dependency>
      <groupId>org.junit.jupiter</groupId>
      <artifactId>junit-jupiter</artifactId>
      <version>5.8.2</version>
      <scope>test</scope>
    </dependency>
  </dependencies>
  <build>
    <plugins>
      <!-- Surefire 插件运行测试 -->
      <plugin>
        <groupId>org.apache.maven.plugins</groupId>
        <artifactId>maven-surefire-plugin</artifactId>
        <version>3.0.0-M5</version>
      </plugin>
    </plugins>
  </build>
</project>

--------------------------------------------------------------------------------

// 文件：src/main/java/com/example/util/HeapSortUtil.java
package com.example.util;

/**
 * HeapSortUtil 提供大顶堆和小顶堆的构建、排序及动态操作方法
 */
public class HeapSortUtil {

    private HeapSortUtil() {} // 私有构造，防止实例化

    // 交换数组中两个元素
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // ------------------ 大顶堆部分 ------------------

    /**
     * 对数组原地构建大顶堆
     * @param arr 待构建堆的数组
     */
    public static void buildMaxHeap(int[] arr) {
        int n = arr.length;
        // 最后一个非叶子节点索引为 n/2 - 1，依次向前 heapify
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapifyMax(arr, n, i);
        }
    }

    /**
     * 对以 root 为根、长度为 heapSize 的子树进行大顶堆调整
     * @param arr      数组
     * @param heapSize 堆大小
     * @param root     根节点索引
     */
    private static void heapifyMax(int[] arr, int heapSize, int root) {
        int largest = root;
        int left  = 2 * root + 1;
        int right = 2 * root + 2;
        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != root) {
            swap(arr, root, largest);
            heapifyMax(arr, heapSize, largest);
        }
    }

    /**
     * 使用大顶堆实现升序排序
     * @param arr 待排序数组
     */
    public static void heapSortAsc(int[] arr) {
        int n = arr.length;
        buildMaxHeap(arr);
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);          // 将当前最大值放到末尾
            heapifyMax(arr, i, 0);    // 重新调整剩余部分为大顶堆
        }
    }

    // ------------------ 小顶堆部分 ------------------

    /**
     * 对数组原地构建小顶堆
     * @param arr 待构建堆的数组
     */
    public static void buildMinHeap(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapifyMin(arr, n, i);
        }
    }

    /**
     * 对以 root 为根、长度为 heapSize 的子树进行小顶堆调整
     * @param arr      数组
     * @param heapSize 堆大小
     * @param root     根节点索引
     */
    private static void heapifyMin(int[] arr, int heapSize, int root) {
        int smallest = root;
        int left  = 2 * root + 1;
        int right = 2 * root + 2;
        if (left < heapSize && arr[left] < arr[smallest]) {
            smallest = left;
        }
        if (right < heapSize && arr[right] < arr[smallest]) {
            smallest = right;
        }
        if (smallest != root) {
            swap(arr, root, smallest);
            heapifyMin(arr, heapSize, smallest);
        }
    }

    /**
     * 使用小顶堆实现降序排序
     * @param arr 待排序数组
     */
    public static void heapSortDesc(int[] arr) {
        int n = arr.length;
        buildMinHeap(arr);
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapifyMin(arr, i, 0);
        }
    }

    // ------------------ 动态堆操作部分 ------------------

    /**
     * 向大顶堆中插入一个新元素（假设堆用 int[] 存储且大小可扩展）
     * @param heap 当前堆数组
     * @param size 堆中已有元素个数
     * @param value 待插入的值
     * @return 插入后堆大小（size+1）
     */
    public static int maxHeapInsert(int[] heap, int size, int value) {
        heap[size] = value;
        int i = size;
        // 向上浮动调整
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[parent] < heap[i]) {
                swap(heap, parent, i);
                i = parent;
            } else {
                break;
            }
        }
        return size + 1;
    }

    /**
     * 从大顶堆中弹出堆顶元素
     * @param heap 当前堆数组
     * @param size 堆中元素个数
     * @return 弹出后堆大小（size-1），堆顶元素存放在 heap[size-1]
     */
    public static int maxHeapExtract(int[] heap, int size) {
        swap(heap, 0, size - 1);
        heapifyMax(heap, size - 1, 0);
        return size - 1;
    }

    /**
     * 向小顶堆中插入一个新元素
     */
    public static int minHeapInsert(int[] heap, int size, int value) {
        heap[size] = value;
        int i = size;
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[parent] > heap[i]) {
                swap(heap, parent, i);
                i = parent;
            } else {
                break;
            }
        }
        return size + 1;
    }

    /**
     * 从小顶堆中弹出堆顶元素
     */
    public static int minHeapExtract(int[] heap, int size) {
        swap(heap, 0, size - 1);
        heapifyMin(heap, size - 1, 0);
        return size - 1;
    }
}

--------------------------------------------------------------------------------

// 文件：src/main/java/com/example/cli/Main.java
package com.example.cli;

import com.example.util.HeapSortUtil;
import org.apache.commons.cli.*;

/**
 * Main 类处理命令行参数，演示堆排序算法
 */
public class Main {
    public static void main(String[] args) {
        Options options = new Options();
        options.addOption(null, "mode", true, "排序模式：asc（升序）| desc（降序）");
        options.addOption(null, "values", true, "待排序整数列表，逗号分隔");

        HelpFormatter formatter = new HelpFormatter();
        CommandLineParser parser = new DefaultParser();
        try {
            CommandLine cmd = parser.parse(options, args);
            String mode = cmd.getOptionValue("mode", "asc");
            String[] parts = cmd.getOptionValue("values", "").split(",");
            int[] arr = new int[parts.length];
            for (int i = 0; i < parts.length; i++) {
                arr[i] = Integer.parseInt(parts[i].trim());
            }

            if ("asc".equalsIgnoreCase(mode)) {
                HeapSortUtil.heapSortAsc(arr);
                System.out.println("升序结果：");
            } else {
                HeapSortUtil.heapSortDesc(arr);
                System.out.println("降序结果：");
            }
            // 打印排序后的数组
            for (int v : arr) {
                System.out.print(v + " ");
            }
            System.out.println();
        } catch (ParseException | NumberFormatException ex) {
            System.err.println("参数解析或格式错误: " + ex.getMessage());
            formatter.printHelp("java -jar heap-sort-demo.jar", options);
        }
    }
}

--------------------------------------------------------------------------------

// 文件：src/test/java/com/example/util/HeapSortUtilTest.java
package com.example.util;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

/**
 * HeapSortUtil 单元测试
 */
public class HeapSortUtilTest {

    @Test
    void testHeapSortAsc() {
        int[] arr = {5, 3, 8, 4, 2};
        HeapSortUtil.heapSortAsc(arr);
        assertArrayEquals(new int[]{2,3,4,5,8}, arr);
    }

    @Test
    void testHeapSortDesc() {
        int[] arr = {5, 3, 8, 4, 2};
        HeapSortUtil.heapSortDesc(arr);
        assertArrayEquals(new int[]{8,5,4,3,2}, arr);
    }

    @Test
    void testDynamicMaxHeap() {
        int[] heap = new int[10];
        int size = 0;
        size = HeapSortUtil.maxHeapInsert(heap, size, 7);
        size = HeapSortUtil.maxHeapInsert(heap, size, 2);
        size = HeapSortUtil.maxHeapInsert(heap, size, 9);
        assertEquals(3, size);
        size = HeapSortUtil.maxHeapExtract(heap, size);
        // 弹出后最后一个位置存放原最大值 9
        assertEquals(2, heap[size]);
        assertEquals(2, size);
    }

    @Test
    void testDynamicMinHeap() {
        int[] heap = new int[10];
        int size = 0;
        size = HeapSortUtil.minHeapInsert(heap, size, 7);
        size = HeapSortUtil.minHeapInsert(heap, size, 2);
        size = HeapSortUtil.minHeapInsert(heap, size, 9);
        assertEquals(3, size);
        size = HeapSortUtil.minHeapExtract(heap, size);
        assertEquals(2, heap[size]);
        assertEquals(2, size);
    }

    @Test
    void testBuildHeapEmpty() {
        int[] arr = {};
        HeapSortUtil.buildMaxHeap(arr);
        HeapSortUtil.buildMinHeap(arr);
        assertArrayEquals(new int[]{}, arr);
    }
}

六、代码详细解读

1. swap 方法
   统一交换数组中两个元素的位置，供各处调用。

2. 大顶堆部分

   • buildMaxHeap：从最后一个非叶子节点 n/2−1 向前，依次对每个子树调用 heapifyMax，将整个数组构建为大顶堆。

   • heapifyMax：对指定根节点 root，与其左右子节点比较，找出最大值索引 largest，若 largest != root，交换并递归调整子树。

   • heapSortAsc：先构建大顶堆，随后将堆顶与末尾元素交换，缩小堆大小并对新根调用 heapifyMax，直至排序完成排列为升序。

3. 小顶堆部分

   • buildMinHeap 与 heapifyMin：与大顶堆相反，确保父节点为最小值。

   • heapSortDesc：基于小顶堆，每次将最小值交换到末尾，生成降序结果。

4. 动态堆操作

   • maxHeapInsert/minHeapInsert：将新元素放在数组末尾，通过向上“浮动”与父节点比较并交换，直到满足堆特性。

   • maxHeapExtract/minHeapExtract：将堆顶与末尾交换，缩小堆大小，并对新根调用对应的 heapify 恢复堆结构；弹出值被放在数组末尾。

5. Main 类

   • 使用 Apache Commons CLI 解析命令行参数 --mode 和 --values。

   • 将输入字符串拆分并解析为整数数组。

   • 根据 mode 调用升序或降序堆排序方法，并打印排序后数组。

6. HeapSortUtilTest 测试类

   • testHeapSortAsc/testHeapSortDesc：验证升降序排序结果与预期相符。

   • testDynamicMaxHeap/testDynamicMinHeap：测试堆插入与弹出功能，确保堆操作正确。

   • testBuildHeapEmpty：验证对空数组调用堆构建无异常且数组保持不变。

---

七、项目详细总结

本项目全面实现了大顶堆与小顶堆的核心功能，包括：

• 原地构建堆（buildMaxHeap、buildMinHeap）；

• 基于堆的升序和降序排序（heapSortAsc、heapSortDesc）；

• 动态堆操作插入与弹出（maxHeapInsert、maxHeapExtract、minHeapInsert、minHeapExtract）；

• 命令行工具演示排序功能；

• 完整的单元测试覆盖各种边界与典型场景。

通过本项目，开发者可以深入理解堆在数组中的索引映射、堆调整（heapify）的递归与迭代实现，以及如何利用堆完成高效排序。同时，动态堆插入与弹出模拟了优先队列的核心操作，为后续实现 PriorityQueue 或其他基于堆的算法（如 Dijkstra、A*）打下基础。

---

八、项目常见问题及解答

Q1：堆排序为何是原地排序？
A：堆排序只在输入数组上进行调整和交换，不需要额外开辟与输入同规模的辅助数组，因此空间复杂度为 O(1)。

Q2：为什么从 n/2 - 1 开始构建堆？
A：数组中索引大于 n/2 - 1 的元素都是叶子节点，不需要 heapify，所以从最后一个非叶子节点开始依次向前保证所有子树满足堆特性。

Q3：堆排序的时间复杂度如何计算？
A：构建堆时间 O(n)，排序阶段每次 heapify 时间 O(log n)，共 n−1 次，整体 O(n + n log n) = O(n log n)。

Q4：动态堆操作中，数组容量如何扩展？
A：本实现假设数组容量足够；在实际使用中可配合 ArrayList 或手动扩容逻辑（如容量翻倍）来支持无限制插入。

Q5：何时使用小顶堆 vs 大顶堆？
A：大顶堆常用于升序排序或实时获取最大值，小顶堆常用于降序排序或实时获取最小值；在优先队列中也按需求选择对应堆结构。

---

九、扩展方向与性能优化

1. 迭代版 heapify
   将 heapifyMax/min 的递归实现改为迭代，避免深度递归带来的函数调用开销。

2. 并行堆构建
   对大规模数据，可尝试并行化初始堆构建阶段，将索引段分发到多个线程分别进行 heapify，然后合并。

3. 基于对象的堆
   将算法泛型化，支持任意实现 Comparable 的对象数组排序，提升通用性。

4. 优先队列封装
   基于本工具类实现通用 PriorityQueue，提供插入、弹出、更新优先级等功能。

5. 性能基准测试
   使用 JMH 对不同数据规模、不同排列状态（随机、有序、逆序）下的堆排序性能进行详细对比，指导实际生产环境选型。

6. 手写内存友好堆
   针对大数据量、内存受限场景，设计外部堆（External Heap）或块式堆，将数据分页载入并堆化，减少内存占用。