通常情况下我们把堆看成是一棵完全二叉树。堆一般分为两种，一种是最大堆，一种是最小堆。最大堆要求根节点的值即大于左子树的值，又大于右子树的值。也就是说最大堆根节点的值是堆中最大的。最小堆根节点的值是堆中最小的，前面我们讲堆排序的时候介绍过堆，实际上他就是数组结构，但因为数组中间有关联，所以我们可以把它当做一棵完全二叉树来看，下面我们再来看一下堆的数据结构是什么样的。
结点中的数字是数组元素的下标，不是数组元素的值。所以如果我们知道父节点的下标我们就可以知道他的两个子节点（如果有子节点），如果知道子节点的下标也一定能找到父节点的下标，他们的关系是：
父节点的下标=（子节点下标-1）>>1；
左子节点下标=父节点下标*2+1；
右子节点下标=父节点下标*2+2；
堆的创建：
堆有两种，一种是最大堆，一种是最小堆。顾名思义，最大堆就是堆顶的元素是最大的，最小堆就是堆顶的元素是最小的。原理都差不多，我们只分析一个就行了，我们就以数组【10，4，8，3，5，1】为例来画个图分析一下最小堆是怎么创建的。
这就是堆的创建，把元素加入到堆中的时候，都要和父节点进行比对，在最小堆中，如果比父节点小，就要和父节点交换，交换之后还要继续和再和新的父节点对比……。同理在最大堆中，如果比父节点大，就要和父节点交换。
我们看到上面堆创建之后数组的元素顺序变为【1，4，3，10，5，8】
堆的删除
堆的添加会往上调整，堆的删除不仅会往下调整而且还有可能往上调整。堆中元素的删除我们可以从堆顶删除，也可以从中间某个位置删除，如果从堆顶删除的话我们只需要往下调整即可，因为堆顶没有父节点，不需要往上调整。如果从中间删除的话，我们先要往下调整，如果往下调整没有成功（比如在最小堆中，他比两个子节点都小），我们还要进行往上的调整。调整的原理就是把数组最后一个元素放到要删除的元素位置上，然后在删除元素的位置上进行上下调整，原理其实都差不多，我们来看一下最小堆顶部元素删除之后的调整。
上面是我们把堆顶元素1删除之后堆的调整，如果我们再把堆顶元素3删除之后，只需要用数组的最后一个元素5替换3，然后再往下调整即可……
代码
堆的添加和删除我们都分析过了，如果把前面的分析都搞懂的话，那么堆的代码就很容易写了，我们来看下
public class MyHeap<E> {
private Object[] data;//数据存放区
private int size;//堆的大小
private Comparator<? super E> comparator;//比较器
public MyHeap(int initialCapacity) {
this(initialCapacity, null);
}
public MyHeap(int initialCapacity, Comparator<? super E> comparator) {
if (initialCapacity < 1)
throw new IllegalArgumentException("堆的大小必须大于0");
this.data = new Object[initialCapacity];
this.comparator = comparator;
}
/**
* @param e 向堆中添加元素
* @return
*/
public boolean add(E e) {
if (e == null)//不能为空
throw new NullPointerException();
if (size >= data.length)//如果堆的空间不够了就扩容，这里是扩大2倍
data = Arrays.copyOf(data, data.length << 1);
if (size == 0)//如果堆是空的，直接添加就可以了，不需要调整，因为就一个没发调整
data[0] = e;
else//如果堆不是空的，就要往上调整。
siftUp(e);
size++;//添加完之后size要加1
return true;
}
public int getSize() {
return size;
}
//删除堆顶元素
public E remove() {
if (size == 0)
return null;
size--;
E result = (E) data[0];//获取堆顶的元素
E x = (E) data[size];//取出数组的最后一个元素
data[size] = null;//然后把最后一个元素的位置置空
if (size != 0)
siftDown(x);//这里实际上是把数组的最后一个元素取出放到栈顶，然后再往下调整。
return result;
}
//访问堆顶元素，不删除
public E peek() {
return (size == 0) ? null : (E) data[0];
}
/**
* 返回数组的值
*
* @param a
* @param <T>
* @return
*/
public <T> T[] toArray(T[] a) {
if (a.length < size)
return (T[]) Arrays.copyOf(data, size, a.getClass());
System.arraycopy(data, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
/**
* 往上调整，往上调整只需要和父节点比较即可，如果比父节点大就不需要在调整
*
* @param e
*/
private void siftUp(E e) {
int s = size;
while (s > 0) {
int parent = (s - 1) >>> 1;//根据子节点的位置可以找到父节点的位置
Object pData = data[parent];
//和父节点比较，如果比父节点大就退出循环不再调整
if (comparator != null) {
if (comparator.compare(e, (E) pData) >= 0)
break;
} else {
if (((Comparable<? super E>) e).compareTo((E) pData) >= 0)
break;
}
//如果比父节点小，就和父节点交换，然后再继续往上调整
data[s] = pData;
s = parent;
}
//通过上面的往上调整，找到合适的位置，再把e放进去
data[s] = e;
}
/**
* 往下调整，往下调整需要和他的两个子节点（如果有两个子节点）都要比较，哪个最小就和哪
* 个交换，如果比两个子节点都小就不用再交换
*
* @param e
*/
private void siftDown(E e) {
int half = size >>> 1;
int index = 0;
while (index < half) {
int min = (index << 1) + 1;//根据父节点的位置可以找到左子节点的位置
Object minChild = data[min];
int right = min + 1;//根据左子节点找到右子节点的位置
if (right < size) {//如果有右子节点就执行这里的代码
//如果有右子节点，肯定会有左子节点。那么就需要左右两个子节点比较，把小的赋值给minChild
if (comparator != null) {
if (comparator.compare((E) minChild, (E) data[right]) > 0)
minChild = data[min = right];
} else {
if (((Comparable<? super E>) minChild).compareTo((E) data[right]) > 0)
minChild = data[min = right];
}
}
//用节点e和他的最小的子节点比较，如果小于他最小的子节点就退出循环，不再往下调整了，
if (comparator != null) {
if (comparator.compare(e, (E) minChild) <= 0)
break;
} else {
if (((Comparable<? super E>) e).compareTo((E) minChild) <= 0)
break;
}
//如果e比它的最小的子节点小，就用最小的子节点和e交换位置，然后再继续往下调整。
data[index] = minChild;
index = min;
}
data[index] = e;
}
}
这里的删除和添加操作的都是堆顶的元素，所以添加的时候会调用siftUp进行往上调整，删除的时候会调用siftDown进行往下调整。我把注释都写在代码中了，这里就不再详细介绍。
堆排序
通过上面的分析，我们知道最大堆就是堆顶元素始终保持的是最大值，最小堆就是堆顶元素始终保持的是最小值，假如在最小堆中我们把堆顶元素一个个给移除不就相当于排序了吗。我们来测试一下
int[] array = {10, 4, 8, 3, 5, 1};
System.out.print("数组原始的值：");
Util.printIntArrays(array);
MyHeap myHeap = new MyHeap(10, new Comparator<Integer>() {
@Override
public int compare(Integer o, Integer t1) {
return (o - t1 > 0) ? 1 : -1;
}
});
for (int i = 0; i < array.length; i++) {
myHeap.add(array[i]);
}
System.out.println();
System.out.print("堆中元素的值：");
Util.printObjectArrays(myHeap.toArray(new Object[myHeap.getSize()]));
System.out.println();
System.out.print("排序之后的值：");
for (int i = 0, length = myHeap.getSize(); i < length; i++) {
System.out.print(myHeap.remove() + "\t");
}
我们来看一下打印结果
1数组原始的值：10 4 8 3 5 1
2堆中元素的值：1 4 3 10 5 8
3排序之后的值：1 3 4 5 8 10
我们看到堆中元素的值是【1，4，3，10，5，8】和我们最开始分析创建堆的结果完全一致。并且最后一行完成了从小到大的顺序输出
总结：
上面我们主要分析是最小堆，如果是最大堆代码该怎么写呢，其实有两种方式，一种是直接在上面代码MyHeap类中修改，还一种是在创建构造函数的时候重写比较器Comparator，我们这里推荐使用第二种，比如我们想按照从大到小的顺序输出，我们来看下该怎么写
int[] array = {10, 4, 8, 3, 5, 1};
System.out.print("数组原始的值：");
Util.printIntArrays(array);
MyHeap myHeap = new MyHeap(10, new Comparator<Integer>() {
@Override
public int compare(Integer o, Integer t1) {
return (o - t1 < 0) ? 1 : -1;
}
});
for (int i = 0; i < array.length; i++) {
myHeap.add(array[i]);
}
System.out.println();
System.out.print("堆中元素的值：");
Util.printObjectArrays(myHeap.toArray(new Object[myHeap.getSize()]));
System.out.println();
System.out.print("排序之后的值：");
for (int i = 0, length = myHeap.getSize(); i < length; i++) {
System.out.print(myHeap.remove() + "\t");
}
我们只需修改一个字符即可，就是在上面第7行把之前的大于号改为小于号，我们来看下运行结果
数组原始的值：10 4 8 3 5 1
堆中元素的值：10 5 8 3 4 1
排序之后的值：10 8 5 4 3 1
最后完全实现了从大到小的输出。
