优先队列与二叉堆
优先队列
优先队列是队列的一种变型，它又有一个别名：堆
我们大家肯定都知道队列，队列遵循FIFO的原则：先出先进。
但是优先队列则不再遵循先入先出的原则，而是分为两种情况：
最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队
最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队
例如有一个最大优先队列，其中的最大元素是8，那么虽然8并不是队头元素，但出队时仍然让元素8首先出队。
那么如何实现呢？就用二叉堆来实现：
二叉堆其实和完全二叉树类似
二叉堆有两种：大顶堆（最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值）、小顶堆（最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值）
因此，可以用最大堆来实现最大优先队列，这样的话，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。
这样入队就是让将元素插入到二叉树中，出队就是删除二叉树的根节点，然后再进行调整，将次之元素补到根节点位置。
二叉堆的自我调整
对于二叉堆，有如下几种操作。
-
插入节点。
-
删除节点。
-
构建二叉堆。
这几种操作都基于堆的自我调整。所谓堆的自我调整，就是把一个不符合堆性质的完全二叉树，调整成一个堆。下面让我们以最小堆为例，看一看二叉堆是如何进行自我调整的。
1、插入节点
当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置。
例如插入一个新节点，值是 0：
这时，新节点的父节点5比0大，显然不符合最小堆的性质。于是让新节点“上浮”，和父节点交换位置。
继续用节点0和父节点3做比较，因为0小于3，则让新节点继续“上浮”。
然后1再与根节点比较，继续上浮。
- 删除节点
二叉堆删除节点的过程和插入节点的过程正好相反，所删除的是处于堆顶的节点。例如删除最小堆的堆顶节点1。
这时，为了继续维持完全二叉树的结构，我们把堆的最后一个节点10临时补到原本堆顶的位置。
接下来，让暂处堆顶位置的节点10和它的左、右孩子进行比较，如果左、右孩子节点中最小的一个（显然是节点2）比节点10小，那么让节点10“下沉”。
继续让节点10和它的左、右孩子做比较，左、右孩子中最小的是节点7，由于10大于7，让节点10继续“下沉”。
这样一来，二叉堆重新得到了调整。
3、二叉堆的调整
构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质就是让所有非叶子节点依次“下沉”。
下面举一个无序完全二叉树的例子，如下图所示。
首先，从最后一个非叶子节点开始，也就是从节点10开始。如果节点10大于它左、右孩子节点中最小的一个，则节点10“下沉”。
接下来轮到节点3，如果节点3大于它左、右孩子节点中最小的一个，则节点3“下沉”。
然后轮到节点1，如果节点1大于它左、右孩子节点中最小的一个，则节点1“下沉”。事实上节点1小于它的左、右孩子，所以不用改变。
接下来轮到节点7，如果节点7大于它左、右孩子节点中最小的一个，则节点7“下沉”。
节点7继续比较，继续“下沉”。
经过上述几轮比较和“下沉”操作，最终每一节点都小于它的左、右孩子节点，一个无序的完全二叉树就被构建成了一个最小堆。
复杂度
堆的插入操作是单一节点的“上浮”，堆的删除操作是单一节点的“下沉”，这两个操作的平均交换次数都是堆高度的一半，所以时间复杂度是O(logn)。
而构建堆的时间复杂度却是O(n)。这涉及数学推导过程，有兴趣的话，可以自己琢磨一下。
ps
还需要明确一点：二叉堆虽然是一个完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。换句话说，二
叉堆的所有节点都存储在数组中。
在数组中，在没有左、右指针的情况下，如何定位一个父节点的左孩子和右孩子呢？
像上图那样，可以依靠数组下标来计算。
假设父节点的下标是parent，那么它的左孩子下标就是2×parent+1；右孩子下标就是2×parent+2。
例如上面的例子中，节点6包含9和10两个孩子节点，节点6在数组中的下标是3，节点9在数组中的下标是7，节点10在数组中的下标是8。
那么，
7 = 3×2+1，
8 = 3×2+2，
刚好符合规律。
/**
“上浮”调整
@param array 待调整的堆
*/
public static void upAdjust(int[] array) {
int childIndex = array.length-1;
int parentIndex = (childIndex-1)/2;
// temp 保存插入的叶子节点值，用于最后的赋值
int temp = array[childIndex];
while (childIndex > 0 && temp < array[parentIndex]) {
//无须真正交换，单向赋值即可
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = (parentIndex-1) / 2;
}
array[childIndex] = temp;
}
/**
“下沉”调整
@param array 待调整的堆
@param parentIndex 要“下沉”的父节点
@param length 堆的有效大小
*/
public static void downAdjust(int[] array, int parentIndex,int length) {
// temp 保存父节点值，用于最后的赋值
int temp = array[parentIndex];
int childIndex = 2 * parentIndex + 1;
while (childIndex < length) {
// 如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
if (childIndex + 1 < length && array[childIndex + 1] <array[childIndex]) {
childIndex++;
}
// 如果父节点小于任何一个孩子的值，则直接跳出
if (temp <= array[childIndex]){
break;
}
//无须真正交换，单向赋值即可
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
array[parentIndex] = temp;
}
/**
构建堆
@param array 待调整的堆
*/
public static void buildHeap(int[] array) {
// 从最后一个非叶子节点开始，依次做“下沉”调整
for (int i = (array.length-2)/2; i>=0; i--) {
downAdjust(array, i, array.length);
}
}
public static void main(String[] args) {
int[] array = new int[] {1,3,2,6,5,7,8,9,10,0};
upAdjust(array);
System.out.println(Arrays.toString(array));
array = new int[] {7,1,3,10,5,2,8,9,6};
buildHeap(array);
System.out.println(Arrays.toString(array));
}