可以把堆看做是一棵完全二叉树。堆一般分为两种，一种是最大堆（有的也叫大根堆，大顶堆），一种是最小堆。最大堆根节点的值是堆中最大的，最小堆根节点的值是堆中最小的。两者原理差不多，这里只介绍其中一种，我们就拿最小堆来讲解。因为堆是一棵完全二叉树，所以如果我们知道子节点的下标，那么一定知道父节点的下标，如果知道父节点的下标也一定知道子节点的下标（假设有子节点），如下图所示。
他们的关系如下：
父节点的下标 = (子节点下标-1) >> 1;
左子节点下标 = 父节点下标*2 + 1;
右子节点下标 = 父节点下标*2 + 2;
堆中添加元素
堆的常见操作有两个，一个是往堆中添加元素，一个是删除堆顶元素。往堆中添加元素实际上相当于在完全二叉树中添加一个叶子节点，添加完之后还需要往上调整，就是和父节点比较谁的值小（这里介绍的是最小堆），如果比父节点小就和父节点交换，交换完之后，还要继续往上比较 …… ，如果比父节点值大就不在交换。如下图所示。
这样通过不断的和父节点比较，如果添加的元素是堆中最小的，他就会跑到根节点，也就是最小堆的根节点是堆中所有元素中最小的。如果添加元素不比父节点小，就不需要交换。
堆中删除元素
堆中元素的添加只需要和父节点比较即可，因为一个节点最多只能有一个父节点（根节点没有父节点）。但堆的删除就点麻烦了，因为如果直接删除，就会把一棵二叉树变成两棵二叉树。实际上堆的删除并不是直接删除，而是让最后一个叶子节点（二叉树最下面一行最右边的节点）替换根节点，然后根节点往下调整，往下调整的步骤就是：
- 如果根节点比他的两个子节点都小，就不需要往下调整。
- 如果其中的一个子节点比根节点小，根节点就和那个比他小的子节点交换，交换完之后继续往下比较。
- 如果根节点比他的两个子节点都大，根节点就和那个最小的子节点交换，交换完之后继续往下比较。
堆的添加会往上调整，堆的删除会往下调整，这里的删除只删除堆顶的元素，如果不是堆顶元素，两个方向都要考虑，我们来看下代码。
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;
}
// 向堆中添加元素。
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];
}
// 往上调整，往上调整只需要和父节点比较即可，如果比父节点大就不需要在调整。
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;
}
// 往下调整，往下调整需要和他的两个子节点（如果有两个子节点）都要比较，
// 哪个最小就和哪个交换，如果比两个子节点都小就不用在交换。
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) {
// 如果有右子节点，肯定会有左子节点。左右两个子节点比较取最小值。
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;
}
}
| 数组，滚动数组，差分数组，树状数组 | |
| 链单向表，双向链表，循环链表，跳表，异或链表 | |
| 队列，循环队列，双端队列 | |
| 栈 | |
| 散列表 | |
| 二叉树，二叉搜索树，AVL树，红黑树，字典树，哈夫曼树，线段树，笛卡尔树 | |
| 堆 | |
| 图的介绍，图的遍历，Dijkstra算法，Bellman-Ford算法，SPFA算法，Floyd算法，Prim算法，Kruskal算法，Boruvka算法，拓扑排序 |
