在算法导论第三版中介绍“堆排序是一种原地排序，如果试图引入数组，那么将失去这一优势。”堆排序的基础是在原有堆上进行排序，即将等待排序的集合先建堆
1.建立最大堆（Max_Heapify）
最大堆满足条件A[Parent[i]]>=A[i]
最大堆唯一能确立的就是数组中的最大元素，相当于一个复杂的Max方法，但是重新确立一个最大堆比较快速
//伪代码片段
Max_Heapify(A,i) l=LEFT(i) r=RIGHT(i) if l<=A.heap-size and A[l]>A[i] largest=l else largest=i if r<=A.heap-size and A[r]>A[largest] largest=r if largest !=i exchange A[i] with A[largest] Max_Heapify(A,largest)
2.堆排序（Heap_Sort）
每次从最大堆中选出第一个元素Array[0]（数组中最大的元素）,将其与最后一个元素Array[n-1]交换,这样最大元素就放到了最后一个位子，接下来就可以把它剔除了，n–1,将刚刚的Arrayn-1在新的最大堆（元素少了一个，挑一个最大的出来）中找到合适的位置。
相当于第一次建立最大堆是建立，剩下的每次都是修补，将交换的元素找到一个合适的位置,这样每次Array[0]又成了最大元素
//伪代码片段
Heap_Sort(A)
Build_Max_Heap(A)
for i=A.length downto 2
exchange A[1] with A[i]
A.heap-size=A.heap-size - 1
Max_Heapify(A,1)
这是基于最大堆排序，结果是从小到大，因为最大的元素放在数组末尾，最小堆排序相反，但原理一样
public class 堆排序 {
// 先建堆
public static void main(String[] args) {
int Array[] = { 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 };
System.out.print("构建最大堆之前: ");
for (int m : Array) {
System.out.print(" " + m);
}
System.out.println("");
Heap_Sort(Array);
System.out.print("堆排序完成之后: ");
for (int m : Array) {
System.out.print(" " + m);
}
}
public static void Heap_Sort(int Array[]) {
int m_size = Array.length - 1;
// Build_Max_Heapify(),将使A[0]达到最大值。这样一直循环交换存放在数组A[i]中，递归调用。
Build_Max_Heapify(Array);// 堆排序算法利用Build_Max_Heapify(Array)将数组Array建成最大堆
System.out.print("构建最大堆之后: ");
for (int m : Array) {
System.out.print(" " + m);
}
System.out.println("");
for (int i = m_size; i >= 1; i--) {
Array[i] += Array[0]; // 因为数组中的最大元素总在根结点Array[0],与Array[m_size}交换，相当于将该节点已经确定出位置，接下来的排序可以不用再考虑该元素（它已经有了最后的位置）
Array[0] = Array[i] - Array[0];
Array[i] -= Array[0];
// swap(A[0], A[i]);
--m_size;// 剔除刚刚交换的Array[m_size]
Max_Heapify(Array, 0,m_size);// 再构建最大堆，在原有的最大堆基础之上乱了一个Array[0]，找到Array[0]的位置，又是一个新的最大堆（少了刚刚那个确立的最大元素）
}
}
public static void Build_Max_Heapify(int A[]) { // 建堆：子数组A[n/2+1...n]中的元素都是叶子节点，因此每个都可以看作只含一个元素的堆.
int m_size = A.length - 1; // m_size/2与m_size一样都正确，也就是上面句子的解释。
for (int i = m_size / 2; i >= 0; i--)
Max_Heapify(A, i,m_size);
}
public static void Max_Heapify(int Array[], int i,int needSize) {
int m_size = needSize;
int largest;
int left = Left(i);
int right = Right(i);
if ((left <= m_size) && (Array[left] > Array[i]))
largest = left;
else
largest = i;
if ((right <= m_size) && (Array[right] > Array[largest]))
largest = right;
if (largest != i) {
Array[i] += Array[largest]; // 第一次交换确立最大元素Array[largest]
Array[largest] = Array[i] - Array[largest];
Array[i] -= Array[largest];
Max_Heapify(Array, largest,m_size); // 将刚刚与最大元素交换的元素Array[i]在最大堆中找到一个合适的位置
}
}
int Parent(int i) { // Parent node
return i / 2;
}
static int Right(int i) { // right node
return 2 * i + 2;
}
static int Left(int i) { // left node
return 2 * i + 1;
}
}