前言：之前在学习二叉堆算法时，感觉自己明白了。但是当我自己去写代码的时候，或者回想的时候，却很难系统的描述出来。在仔细研究源码之后，发现了一些之前没有发现的新东西，特地，记录下来，供大家参考。
文章目录
二叉堆原理二叉堆的应用二叉堆操作具体实现总结二叉堆原理
二叉堆类似于完全二叉树。不过与二叉树不同之处在于，二叉堆底层是数组，其左右子节点和父节点的关联是通过索引建立。例如当前节点的元素为arr[index]，如果该元素有子节点，那么左子节点为arr[2*index + 1], 右子节点为arr[2*index + 2].同理 ，如果index > 0, 那么该元素的父节点为arr[(index- 1)/2].
这是二叉树的精髓所在：通过数组索引将父节点和子节点建立其联系
下面用一个图，清晰表示二叉树元素之间的关系
二叉堆的应用
之所以要谈到二叉堆的应用，在于二叉堆有个非常独特的特征。二叉堆可以分为大根堆和小根堆。所谓大根堆，就是，父节点的值大于等于左右子节点的值，这样大根堆的堆顶（即数组的第一个数）是数组的最大值，如上图所示。而小根堆就是，父节点的值小于等于左右子节点的值，这样小根堆的堆顶（即数组的第一个数）是数组的最小值。由于这样的特性， 二叉堆被用于实现优先队列（Java中有源码）。
二叉堆操作
二叉堆的操作可以分为两大部分，所以代码也是围绕这两个操作进行。
添加元素
当添加元素时，首先会在堆尾处添加，为了使添加后的新堆也满足大根堆（或者小根堆）的特征，就需要对新添加的元素进行操作（此处命名为“上浮”），大致的过程为：以大根堆为例，将该元素与其父节点进行比较，如果比父节点大，则于其交换位置，并接着和上面的父节点再对比，依次类推，直到堆顶元素。
删除元素（注意：通常指删除堆顶元素）
删除元素时，进行的操作为： 将堆顶元素，替换为堆尾元素，接着将堆尾元素下沉，和左右子节点比较， 如果比两者都大，就将堆尾元素存放在堆顶，否则将子节点中的最大值放在堆顶，接着和原先子节点所在索引位置的子节点进行比较，重复以上操作。使其满住大根堆的特征。
过程，以图片形式展现一下，图中是以小根堆为例。
将数组[23,56,40,62,38,55,10,16]的中的元素依次插入堆中的过程。
删除堆顶的操作，具体流程如下
具体实现
首先从添加元素开始，实现二叉堆（以最大堆为例）。
public class BinaryStackTest {private Integer[] queen; // 数组队列， 实现最大堆private int size; // 即记录当前堆尾部的位置也记录堆中的元素，初始值为0，未添加元素private final int DEFAULT_INITIAL_CAPACITY = 11; //默认初始容量public BinaryStackTest (){// 构造器this(DEFAULT_INITIAL_CAPACITY );}public BinaryStackTest (int capacity){// 构造器重载this.queen = new Integer[capacity];}}
上面代码已经将基本属性全部赋值。
接下来为具体方法实现。
向堆中添加元素
/*** 向堆中添加元素* @param e* @return*/public boolean add(int e){int k = size; //当前元素存放在数组中的位置,如果第一次添加，此处size = 0;// // 存在容量不足问题，此处不去关注，可以去看java中源码，非常简单siftUp(k, e, queen); // 将当前元素上浮size++; // 当前队列中的元素个数 + 1return true;}
接下来实现上浮操作
/*** 将元素进行上浮，使得堆满足最大堆* @param k* @param e* @param es*/private void siftUp(int k, int e, int[] es) {while (k > 0){ // 一直循环到堆顶元素int parent = (k-1) >>> 1; // 找到父节点的索引,通过移位的方式等效除以2；if (es[parent] > e){break;}es[k] = es[parent]; // 将其父节点的值 存放在当前位置k = parent; // 将指针指向父节点位置}es[k] = e; // 找到新添加元素位置后， 存放该元素}
这样当向堆中添加元素时，就会满住最大堆的性质。
为了观察数组的元素排列，添加这方法：
public int[] getQueen(){return queen;}
测试一下效果：
BinaryStackTest BinaryStackTest = new BinaryStackTest ();int[] arr = new int[]{1, 2, 3, 4, 5};for (int e: arr){stackSortTest.add(e); // 依次往堆中添加元素}int[] queen = stackSortTest.getQueen();System.out.println(Arrays.toString(queen));
输出结果
[5, 4, 2, 1, 3, 0, 0, 0, 0, 0, 0]
ok,至此，添加元素的操作，我们就解决了。
第二步，解决删除操作
/*** 删除操作: 删除堆顶元素* @return*/public int poll(){final int[] es;int result = 0;if(size > 0){// 判断数组中是否有元素result = (es = queen)[0] // 堆顶元素int n = --size; // 数组中元素总量少1，此处n表示堆尾元素的索引int x = es[n]； // 堆尾元素if(n > 0){// 判断是否删除后，数组中没有元素了siftDown(0, es, x, n); // 下沉此元素}}return result;}
接着解决最后一个方法，下沉操作.。这个方法细节还比较多，多看几遍。
public void siftDown(int k, int[] es, int x, int n){int half = n>>>1 ; // 确保下面循环的节点非叶节点while(k < half){int child = (k <<1) + 1; // 左节点int c = es[child]; // 左节点元素int right = child ＋1 ; // 右节点元素if(right < n && es[right] > c){child = right; // 确保child为子节点最大值的索引c = es[child] // 确保c为子节点最大值}es[k] = c;k = child; //此处将k指向下个子节点位置}es[k] = x; //最终x存放的位置}
上面要注意这一行的意思：
int half = n>>>1 ; // 确保下面循环的节点非叶节点
通过图片来说明：
假设现在删除一下节点的堆顶元素。
那么程序的执行过程为：
总结
二叉堆，最重要的两个操作就是上浮和下沉。上浮用于二叉堆插入数据的情况，下沉用于二叉堆删除堆顶元素时。只要理解这两个操作，便就理解了二叉堆。
