前言
今天在看??ThreadPoolExecutor???的介绍时，看到了它的??workQueue??中有一种优先任务队列，本质上是一个二叉堆(最多有2个孩子节点)。今天就来开始分析一下二叉堆这种数据结构
优先队列
和队列类似，但是出队的元素是优先级最高的元素。如下图所示，我们定义元素值越小，优先级越高。
优先队列一般用二叉堆来实现。
完全二叉堆
完全二叉堆就结构性质上来说就是一个完全填满的二叉树，满足结构性和堆序性。
结构性逻辑上，等同于完全二叉树物理上，借助于向量(底层是数组)实现堆序性父节点的值总是大于或等于（小于或等于）任何一个子节点的值，且每个节点的左子树和右子树都是一个二叉堆。
若父节点的值总是大于(或等于)子节点的值，我们称这种堆为大顶堆；若总是小于(或等于)子节点的值，称为小顶堆。
下图是一个小顶堆的示例图：
其对应的数组表示如下：
可以看到，与上面二叉树的层次遍历次序完全一致，我们定义第一个元素从下标1开始，因此0位置是没值的。
在这种表示下，很容易计算出下标为i的左孩子以及右孩子的位置(下标)：
左孩子： 2 * i右孩子：2 * i + 1
比如，节点5的下标为5(真的只是巧合)，其左孩子下标为10，值为6；右孩子下标为11，值为10。 且上面的堆元素个数???size???为11，有孩子的节点满足??2 * i <= size??
插入
那么如果构造这样一颗完全二叉堆呢？先从插入开始了解
为了插入新节点，将新节点追加到数组最后的位置。这样做的好处是，可以使得结构性得以延续，若堆序性也能保持，则插入完成。
但是，通常情况下，新加入的节点会破坏堆序性。 并只是与其父节点违反堆序性，将其与父节点换位，若满足堆序性，则插入完成；否则继续与(新)父节点换位。 这样一种过程称为上滤。
假设，已存在一个这样的小顶堆，如何插入新节点2呢？ (为了好画图，把上图的10删除先…)
将新节点(节点2)放入堆的最后一个位置
然后执行向上过滤的操作:
如果小于父节点，则与父节点交换位置重复直到大于父节点或者达到堆顶
如上图所示，新加入的节点比父节点5小，交换；继续与新父节点4比较，交换；继续与新父节点1比较，不需要交换，插入完成。
删除
最小元素始终在堆顶，因此可以直接删除，但是这破坏了结构性。
为了保持结构性，通常的做法是，把最末元素移到堆顶上去。但是很有可能会破坏堆序性：
若新的节点与其子节点违反了堆序性，则将新节点与其最小子节点换位若交换后堆序性恢复，则完成；否则继续上一步操作
这个过程称为下滤。
下面通过图示来描述：
首先，删除掉堆顶后，把最末尾的元素移动到堆顶，形成上图堆1；此时破坏了堆序性，因此与最小的子节点3交换 ，上图堆2； 此时，可以看到还是不满足堆序性，继续与最小的子节点8交换，得到上图堆3，此时已经没有子节点了，并且满足了堆序性，操作完成。
批量建堆
回顾删除算法，任意给定堆h1和h2，以及节点p。
其中堆h1和h2是满足堆序性和结构性的完全二叉堆，为了得到h1和h2以及节点p组成的新堆，
只需将h1和h2当成p的子堆，对p进行下滤，这样就能得到想要的新堆。
基于这个思想，我们自下而上、自右而左，依次下滤每个内部节点(不包括叶子节点，叶子节点也不能下滤了)， 这种操作可理解为子堆的逐层向上合并。
@Testpublic void testBuildHeap() { List<Integer> list = IntStream.range(1,10).boxed().collect(Collectors.toList()); Collections.shuffle(list); System.out.println(list);//[2, 6, 8, 7, 9, 5, 3, 4, 1] BinaryHeap<Integer> heap = new BinaryHeap<>(list.toArray(new Integer[]{})); System.out.println(heap);//[1, 2, 3, 4, 9, 5, 8, 6, 7]}
通过程序生成1-9的9个数字，然后进行洗牌操作。我们利用这个随机生成的数组来讲解 批量建堆操作：
首先按照层次遍历的顺序构建一个堆，同样舍弃索引为0的位置。可以看到，结构性满足，但是堆序性是不满足的，为啥，最小的1都到了最下面了。
上图所示是所有的内部节点，我们按照自下而上、自右而左的顺序，依次下滤每个内部节点。首先下滤最后一个内部节点，9/2=4 对应的值为7，这里我们详细说一下，其左右孩子都是只有一个节点的堆，因此，一个节点的堆满足完全二叉堆的条件。对7进行下滤：
接下来是值为8的节点：
按照顺序，然后是值为6的节点,注意这里交换了两次(??6<->1,6<->4??)，为了简单我就没把每一步都画出来了：
最后是值为2的节点，先不着急，我们回顾一下，这个算法有一个特点是，已经处理的左右节点都保持了完全二叉堆的特性。然后对2进行下滤操作，1、3中最小的是1，因此2与1换位：
代码package com.algorithms.heap;/** * 堆是一颗完全填满的二叉树，底层可能未被填满，但是元素是从左到右填入的，这样的树称为完成二叉树。 * <p> * 小顶堆：最小元素在根上，任意子树也要满足这个性质。这里 * * @author yjw * @date 2019/4/23/023 */@SuppressWarnings(“unchecked”)public class BinaryHeap<E extends Comparable<? super E>> implements Heap<E> { /** * 堆中元素数 */ private int size = 0; /** * 索引为0的位置不存任何元素 */ private E[] array; public BinaryHeap() { this(DEFAULT_CAPACITY); } public BinaryHeap(int capacity) { array = (E[]) new Comparable[capacity + 1]; } public BinaryHeap(E[] items) { size = items.length; array = (E[]) new Comparable[(size + 2) * 11/10]; int i = 1;//第一元素 for (E item : items) { array[i++] = item; } buildHeap(); } public BinaryHeap(Iterable<E> items) { this(); items.forEach(this::insert); } /** * 构建堆 * 通过size/2次下滤操作构建堆 */ private void buildHeap() { for (int i = size / 2; i > 0 ; i–) { percolateDown(i); } } @Override public void insert(E x) { if (size == array.length – 1) { ensureCapacity(array.length * 2 + 1); } int hole = ++size; array[0] = x;//必须设置array[0]，否则循环跳不出，或报空指针 while (x.compareTo(array[hole/2]) < 0) { //往上冒 array[hole] = array[hole/2]; hole = hole/2; } array[hole] = x; } /** * 扩容 * @param newCapacity */ private void ensureCapacity(int newCapacity) { E[] oldArray = array; array = (E[]) new Comparable[newCapacity]; for (int i = 1; i < oldArray.length; i++) { array[i] = oldArray[i]; } } @Override public E findMin() { return array[1]; } @Override public E deleteMin() { if (isEmpty()) { throw new IllegalArgumentException(); } E min = findMin();//缓存最小元素 array[1] = array[size–];//用最后一个元素替代最小元素的位置,此时最小元素已经被覆盖了，但是我们通过min变量缓存起来了 percolateDown(1);//进行下滤操作 return min; } /** * 下滤操作 * 由于是小顶堆，每次取孩子中最小的元素替换父节点的位置 * @param hole 待下滤的节点位置 */ private void percolateDown(int hole) { int child; E tmp = array[hole]; while (hole * 2 <= size) { //如果有孩子，hole不停的往下，直到不满足堆的性质 child = hole * 2; //若有右孩子，且右孩子更小 if (child != size && array[child +1].compareTo(array[child]) < 0) { child++;//取右孩子 } if (array[child].compareTo(tmp) < 0) { //hole位置填充最小孩子节点的值 array[hole] = array[child]; hole = child;//继续比较 } else { break; } } array[hole] = tmp; } @Override public boolean isEmpty() { return size == 0; } @Override public void makeEmpty() { for (int i = 1; i <=size; i++) { array[i] = null; } size = 0; }}
??Heap??接口代码:
public interface Heap<E> { int DEFAULT_CAPACITY = 10; void insert(E x); E findMin(); E deleteMin(); boolean isEmpty(); void makeEmpty();}
【本文来自：日本服务器 jap.html 复制请保留原URL】爱人，却不一定能够听懂。他们听见的，多是抱怨不休，心烦意乱。
