大顶堆：堆可以看做一个完全二叉树，如果该完全二叉树满足双亲结点大于等于孩子结点，则这样的堆也称为大顶堆。
小顶堆：如果完全二叉树满足双亲结点小于等于孩子结点，则这样的堆也称为小顶堆。
对于一个数组生成的完全二叉树，如果完全二叉树中的一个节点对应数组中的下标索引为index,则这个节点的左右子节点对应数组中的下标索引为：
left = index * 2 + 1
right = index * 2 + 2 保证 left<arr.length;
则数组生成大顶堆的实现代码如下：
public static void maxHeap(int[] arr, int size, int index){//左子节点int leftNode = 2*index +1;//右子节点int rightNode = 2*index +2;int max = index;//和两个子节点对比，找出最大的一个节点if(leftNode<size&&arr[leftNode]>arr[max]){max = leftNode;}if(rightNode<size&&arr[rightNode]>arr[max]){max = rightNode;}//交换位置if(max != index){int temp = arr[index];arr[index] = arr[max];arr[max] = temp;//递归调用maxHeapmaxHeap(arr,size,max);}
}
//测试用例
public static void main(String[] args){int[] arr = new int[]{9,6,8,7,0,1,10,4,2};//开始位置时最后一个非叶子节点，即最后一个节点的父节点int start = (arr.length-1)/2;//调整为大顶堆for(int i=start; i>=0; i--){maxHeap(arr, arr.length, i);}
}
然后是堆排序：
1、数组中的下标索引依次对应完全二叉树的节点，然后把完全二叉树变成大顶堆，这样数组中的第一个元素就是完全二叉树根节点的值。
2、把数组中的第一个元素与第arr.length个元素交换位置，然后对前arr.length-1个元素重新生成大顶堆。以后依次把第一个元素与第arr.length - i 个元素交换位置。直到arr.length - i =1。
3、此时的数组就是进行升序排序后的数组。如果进行降序排序，可以选择小顶堆的方式。
实现代码如下：
public static void maxHeap(int[] arr, int size, int index){//左子节点int leftNode = 2*index +1;//右子节点int rightNode = 2*index +2;int max = index;//和两个子节点对比，找出最大的一个节点if(leftNode<size&&arr[leftNode]>arr[max]){max = leftNode;}if(rightNode<size&&arr[rightNode]>arr[max]){max = rightNode;}//交换位置if(max != index){int temp = arr[index];arr[index] = arr[max];arr[max] = temp;//递归调用maxHeapmaxHeap(arr,size,max);}
}
//堆排序
public static void HeapSort(int[] arr) {//开始位置时最后一个非叶子节点，即最后一个节点的父节点int start = (arr.length-1)/2;//调整为大顶堆for(int i=start; i>=0; i--){maxHeap(arr, arr.length, i);}//取出最大值，继续调整剩下的为大顶堆for(int j = arr.length-1; j>=0; j--) {int temp = arr[0];arr[0] = arr[j];arr[j] = temp;maxHeap(arr,j,0);}
}