堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
以最小堆为例
对于一个非叶子节点的下沉操作指的是：如果父节点大于子节点的任何一个节点，那么父节点就要和子节点中的最小的节点交换。
代码描述
/**
* 下沉操作，构造小顶堆
* @param heap 元素数组
* @param k 当前元素下标
* @param n 数组长度
*/
public void sink(int[] heap,int k,int n) {
while (k<<1 <= n) {
int j = k<<1;
/**
* 判断左子树大还是右子树大，（当然了，对于小顶堆来说，j指向较小的那个元素）
*/
if (j < n && compare(heap,j, j+1))
j++;
/**
* 判断父节点是否大于最小的子节点，如果如果是则交换，不是则返回
*/
if (!compare(heap,k, j))
break;
exchange(heap,k, j);
k = j;
}
}排序过程
排序的第一步是对整个无序数组进行整理使其满足二叉堆的性质，这样才能对其进行排序（对于非叶子节点所有的父节点均大于其子节点）。
然后对整个堆进行排序，过程描述如下：
对于小顶堆来说，根节点就是堆中最小的元素，把根节点（数组第一个元素）与数组最后一个元素交换，此时堆元素的长度-1
交换以后的数组可能不满足堆的性质，则以根节点开始进行下沉操作，直到数组满足堆得性质。
然后继续交换第一个节点与最后一个节点，如此反复，直到数组中只有一个节点，排序结束
代码描述
/**
* 排序
* 首先对一个无序的数组进行下沉操作，以至于满足堆的性质，（所有的父节点均大于其子节点）
* 然后对整个堆进行排序
* @param heap
*/
public void sort(int[] heap) {
int n = heap.length-1;
/**
* 第一个for循环用户构造一个满足堆特点的二叉堆
* 对所有的非叶子节点执行下沉操作
*/
for (int k = n>>1; k >= 1; k--)
sink(heap, k, n);
/**
* 对二叉堆进行堆排序
* 对于小顶堆来说，根节点就是堆中最小的元素，把根节点（数组第一个元素）与数组最后一个元素交换，此时堆元素的长度-1
* 交换以后的数组可能不满足堆的性质，则以根节点开始进行下沉操作，直到数组满足堆得性质。
* 然后继续交换第一个节点与最后一个节点，如此反复，直到数组中只有一个节点，排序结束
*/
while (n > 1) {
exchange(heap, 1, n--);
sink(heap, 1, n);
}
}完整代码：
package club.test;
import org.junit.Test;
/**
* 堆排序（小顶堆为例）
* @author jiajia
*
*/
public class TestMain8 {
@Test
public void test() {
int[] a=new int[] {0,2,8,5,3,6};
sort(a);
for(int i=0;i<a.length;i++) {
System.out.print(a[i]+" ");
}
}
/**
* 排序
* 首先对一个无序的数组进行下沉操作，以至于满足堆的性质，（所有的父节点均大于其子节点）
* 然后对整个堆进行排序
* @param heap
*/
public void sort(int[] heap) {
int n = heap.length-1;
/**
* 第一个for循环用户构造一个满足堆特点的二叉堆
* 对所有的非叶子节点执行下沉操作
*/
for (int k = n>>1; k >= 1; k--)
sink(heap, k, n);
/**
* 对二叉堆进行堆排序
* 对于小顶堆来说，根节点就是堆中最小的元素，把根节点（数组第一个元素）与数组最后一个元素交换，此时堆元素的长度-1
* 交换以后的数组可能不满足堆的性质，则以根节点开始进行下沉操作，直到数组满足堆得性质。
* 然后继续交换第一个节点与最后一个节点，如此反复，直到数组中只有一个节点，排序结束
*/
while (n > 1) {
exchange(heap, 1, n--);
sink(heap, 1, n);
}
}
/**
* 交换元素
* @param heap
* @param i
* @param j
*/
public void exchange(int[] heap,int i,int j) {
heap[i]=heap[i]+heap[j];
heap[j]=heap[i]-heap[j];
heap[i]=heap[i]-heap[j];
}
/**
* 比较
* @param heap
* @param i
* @param j
* @return
*/
public boolean compare(int[] heap,int i,int j) {
return heap[i]>heap[j]?true:false;
}
/**
* 下沉操作，构造小顶堆
* @param heap 元素数组
* @param k 当前元素下标
* @param n 数组长度
*/
public void sink(int[] heap,int k,int n) {
while (k<<1 <= n) {
int j = k<<1;
/**
* 判断左子树大还是右子树大，（当然了，对于小顶堆来说，j指向较小的那个元素）
*/
if (j < n && compare(heap,j, j+1))
j++;
/**
* 判断父节点是否大于最小的子节点，如果如果是则交换，不是则返回
*/
if (!compare(heap,k, j))
break;
exchange(heap,k, j);
k = j;
}
}
}