此处所说的堆，是数据结构中的堆，而不是JVM运行时数据区域的那个堆。本篇主要讲解数据结构中堆的实现、原理、使用等。
定义堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：“给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于（或大于等于）C的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。
在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。
实际上是说了堆的以下特点：
堆是一种树状结构（逻辑结构）满足“每个节点都大于等于其父节点（根节点除外）”的堆称为最小堆满足“每个节点都小于等于其父节点（根节点除外）”的堆称为最大堆往往用于优先级队列一图胜千言，看下典型的堆结构便知。
可以看出除了根节点外，每个节点都满足节点值大于等于其父亲节点的值，所以这是一个最小堆。
堆的逻辑结构往往是一棵完全二叉树，即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。堆的存储结构（物理结构）往往是一个数组，也就是二叉树从根节点开始进行层次遍历（广度优先遍历）得到的结果，所以上述最小堆的存储结构如下：
[16, 18, 20, 20, 24, 34, 36, 28, 30, 26, 29, 42, 41]从数组看，存储的元素毫无规律。仔细分析节点的父子关系和数组的下标可以得出如下性质：
数组中下标为k（k > 0）的元素，其父节点的下标为(k - 1) / 2数组中下标为k的元素，其左孩子的下标为k * 2 + 1（如果有左孩子的话）数组中下标为k的元素，其右孩子的下标为k * 2 + 2（如果有右孩子的话）根据这些性质，可以构建出一个最小堆的实现
最小堆 定义 /** * 最小堆 */public class MinHeap<E extends Comparable<E>> { /** * 此处是之前博客中实现的ArrayList，并非JDK提供的ArrayList * 实现过程：https://blog.csdn.net/Baisitao_/article/details/102575180 * 源代码：https://github.com/Sicimike/note/blob/master/source/ArrayList.java */ private ArrayList<E> data; public MinHeap(int initCapacity) { data = new ArrayList(initCapacity); } public MinHeap() { data = new ArrayList(); }}因为之前的ArrayList代码中维护的size，所以这里也不再需要。
核心方法根据上文提到了三个性质（父子关系和数组下标），可以先实现相关的方法
/** * 根据子节点找到父节点 * * @param child * @return */private int parent(int child) { if (child <= 0 || child > size()) { throw new IllegalArgumentException("illegal argument:" + child); } return (child - 1) / 2;}/** * 根据父节点找到左子节点 * * @param parent * @return */private int left(int parent) { return parent * 2 + 1;}/** * 根据父节点找到右子节点 * * @param parent * @return */private int right(int parent) { return parent * 2 + 2;}/** * 查看堆中的最小元素 * 因为是最小堆，所以就是data.get(0) * * @return */public E min() { return data.get(0);} add(E e)方法add(E e)方法用于往堆中添加元素，先用图解的方式，来看下往堆中添加元素的过程：
整个过程可以分成两步：
1、新增节点插入二叉树中，也就是数组的尾部
2、循环比较新增节点和其父亲节点的大小，适当的时候交换其与父亲节点的位置
其实现如下：
/** * 添加元素 * * @param e */public void add(E e) {// 容量不够会自动扩容 data.add(e); siftUp(size() - 1);}/** * 把节点上浮（siftUp）到合适的地方 * * @param index */private void siftUp(int index) { while (index > 0 && data.get(index).compareTo(data.get(parent(index))) < 0) { // 当前节点的元素小于父节点的元素，需要上移（交换） data.swap(index, parent(index)); // 更新当前元素的index index = parent(index); }} extractMin()方法extractMin()方法用于删除最小堆的根节点，继续用图解的方式，来看下删除最小堆中根节点的过程：
可以看到整个过程分为三步：
1、把根节点和最后一个节点交换位置
2、删除最后一个节点（也就是之前的根节点）
3、循环下沉根节点
其实现如下：
/** * 移除并返回最小的元素 * * @return */public E extractMin() { // 获取最小的元素用于返回 E result = min(); // 把最小的元素和最后一个元素交换位置 data.swap(0, size() - 1); // 删除最后一个元素（最小值） data.remove(); // 堆顶元素下沉到合适的位置 siftDown(0); return result;}/** * 把节点下沉（siftDown）到合适的地方 * * @param index */private void siftDown(int index) { while (left(index) < size()) { // 要下沉的节点还有左孩子 int k = left(index); if (right(index) < size() && data.get(right(index)).compareTo(data.get(left(index))) < 0) { // 当前节点有右孩子，且右孩子的值小于左孩子的值，则把右孩子记录为待交换的节点k，否则记录左节点为k // 因为是最小堆，所以需要找出两个孩子节点（如果有右孩子）中比较小的那个进行交换 k = right(index); } if (data.get(index).compareTo(data.get(k)) <= 0) { // 如果下沉的节点已经小于或者等于两个子节点中比较小的那个，结束循环 break; } // 当前节点的值大于k节点的值，进行交换 data.swap(index, k); index = k; }} heapify()方法heapify()方法是将任意一个数组调整成堆的形式。要想实现这个功能，可以从数组第二个元素开始，对每个元素执行上浮(siftUp)操作。
除了这种操作之外，还有一种更高效的实现方式，那就是heapify：从最后一个非叶子节点开始，从下往上，对每个节点执行下沉(siftDown)操作，这样一开始就排除了一半的节点。具体实现如下（构造方法的形式实现）：
Github：MinHeap.java
本篇实现的是最小堆，同理可以实现最大堆。文章开始就说过，堆往往用于优先级队列，在JDK源码的优先队列中也能看到堆的实现。