1.数据结构——堆（Heap）
堆是计算机科学中一类特殊的数据结构的总称，是可以看成一棵树的数组对象。
堆总是满足以下两条性质：
1.堆中的每一个节点都满足其值总是大于或小于它的所有子结点。
2.堆总是一棵完全二叉树。
如果堆的每一个节点满足其值总是大于它的孩子结点，则堆为大顶堆，如果堆的每一个节点满足其值总是小于它的孩子结点，则堆为小顶堆。
2.算法思想
堆排序（）是指利用堆这种数据结构所设计的一种排序算法。堆排序的基本思想是：将待排序序列构造成一个大顶堆（或小顶堆）堆排序算法java-堆排序算法（Java实现），此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，在根节点处就可以得到一个次大值，如此反复执行，重复n次堆排序算法java堆排序算法java，便能得到一个有序序列了。它的平均时间复杂度为O（nlogn）。
构造大顶堆或小顶堆时，采用的是由下而上构造堆的思想，先将每个节点的左右子树构造成堆，然后再将该节点与其左右子堆合并成一个大堆，以此由下而上将整棵树构造成小堆顶或大顶堆。
代码实现：
<p><pre>class heap{
//堆排序
public int[] heapSort(int[]A){
for(int i=A.length;i>=1;i--){
//将数组前i个数的最大值提取到数组第一个位置
getTopMax(A,i);
//将这个最大值置换到数组的末尾
int temp=A[0];
A[0]=A[i-1];
A[i-1]=temp;
}
return A;
}
//提取数组[0,len]区间内的最大值
public void getTopMax(int[]A, int len){
//找到树中最后一个非叶子节点的位置
int pos=len/2-1;
for(int i=pos;i>=0;i--){
//得到当前节点的左右孩子节点对应的下标（如果不存在则赋值为当前节点下标）
int left=2*i+1>=len?i:2*i+1;
int right=2*i+2>=len?i:2*i+2;
/**
* 取出该节点及其左右孩子节点中的最大节点值，置换到该节点的位置，
* 保证该节点的值比其左右孩子的值要大
*/
if(A[i]