堆排序是一种基于比较的排序算法，它通过构建和调整二叉堆来实现数据的排序。在二叉堆中，每个父节点的值都大于或等于其子节点的值，这样的堆被称为最大堆。堆排序的基本步骤包括建堆、交换根节点与最后一个元素、减小堆的大小并重新调整堆的过程，这个过程反复执行直至完成排序。
实验目的：
1. 理解数组上不同排序算法的工作原理和实现方法。
2. 熟悉快速排序的单趟排序思路，尽管这里提到的是快速排序，但实际任务是堆排序。
3. 掌握堆排序的时间复杂度，它是O(n log n)，并且对输入数据的顺序不敏感。
实验要求：
1. 设计堆排序的算法，这包括建立最大堆、交换堆顶元素与末尾元素以及调整堆的过程。
2. 应用堆排序对无序数据进行排序，并分析其性能，比如比较平均和最坏情况下的时间效率。
数据输入与输出：
输入数据由多组整数构成，每组数据的个数在输入时给出，最后一组数据以0结束。例如，输入"8"表示接下来有8个整数要排序，然后输入这些整数，之后再输入另一组数据的个数，如"5"，并输入这5个整数，直到输入0结束程序。每组数据数量不超过10万。
输出应按照升序排列的整数列表，每组数据之间用空行分隔，同一组数据之间用空格分隔。测试时，可以使用文件重定向的方式输入10万个无序的整数数据。
程序模板提供了一个基础的堆排序框架，包含两个函数：
1. `HeapSort`：这是堆排序的主要实现，接受一个类型为`type`的数组`arr`和数组大小`n`作为参数。它应该首先调用`HeapAdjust`来构建最大堆，然后不断交换堆顶元素与末尾元素，缩小堆的大小并重新调整堆，直到所有元素都被排序。
2. `HeapAdjust`：此函数用于调整堆，确保堆的性质得到维护。它接受数组`arr`，起始索引`s`和中间索引`m`作为参数。它应该从根节点开始遍历，如果当前节点小于其子节点，则交换它们，然后递归地检查子节点是否满足堆的性质。
在`main`函数中，读取每组数据的个数`m`，然后输入这些整数，调用`HeapSort`进行排序，输出排序后的结果，然后继续处理下一组数据，直到输入0为止。
为了确保堆排序的正确性，需要对`HeapSort`和`HeapAdjust`函数进行调试，确保它们在各种输入情况下都能正确地建立和调整堆，以及正确地输出排序结果。教师评阅环节则需要对程序的正确性、效率和代码质量进行评估。
