数据结构与算法学习笔记 - 优先队列、二叉堆、左式堆
6.1 模型
优先队列是允许至少下列两种操作的数据结构：insert 以及 deleteMin（找出、返回并删除优先队列中最小的元素）。
insert 操作等价于 enqueue（入队），而 deleteMin 则是运算 dequeue（出队)在优先队列中的等价操作。
一些简单的实现
可以使用简单链表进行不排序的插入，则插入操作为 O(1)，但是删除需要遍历链表为 O(N)。
另一种方法是让链表保持排序状态：插入代价高昂 O(N)，但删除为 O(1).但是 deleteMin 的操作比插入操作少，前者可能更好。
另外一种方法是使用二叉查找树，它对这两种操作的平均运行时间都为 O(log N)。
但是，由于我们删除的唯一元素是最小元，反复出去左子树的节点会损害树的平衡使得右子树加重，在最坏情况下 deleteMin 将左子树删空。
另外，使用查找树有很多我们数据结构不需要的链。
二叉堆
我们将要使用的数据结构叫做二叉堆（binary heap），它的使用对于优先队列的实现相当普遍，以至于堆（heap）这个词不加修饰的用在优先队列的上下文中时，一般都是指数据结构的这种实现。
二叉堆有两个性质：结构性和堆序性。
结构性质
堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树被称为完全二叉树（complete binary tree）。
一棵高为 h 的完全二叉树有 2h 到 2h+1 - 1 个节点。它的高度为 Log N，显然它是 O(log N)。
因为二叉堆是满二叉树，所以在高度为 h-1 的树包含
20 + ... + 2h-1 = 2h -1 个元素，
在高度为 h 的层上有 1 至 2h 个元素，所以应该有 2h 至 2h+1 - 1 个元素。
因为完全二叉树这么有规律，所以它可以用一个数组表示而不需要使用链。
对于数组中任意位置 i 上的元素，其左儿子在位置 2i 上，右儿子在左儿子后的单元 (2i + 1)上。它的父亲则在位置 [i / 2] 上。
堆序性质
让操作快速执行的性质是堆序性质（heap-order property）。由于我们想要快速找出最小元，因此最小的元应该在根上。如果我们考虑任意子树也应该是一个堆，那么任意节点就给应该小于它的所有后裔。
基本的堆操作
insert（插入）
为了将一个元素 X 插入到堆中，我们在下一个可用位置创建一个空穴，否则该堆将不是完全树。如果 X 可以放在该空穴中而并不破坏对的序，那么插入完成。
否则，我们把空穴的父节点移入该空穴中，这样空穴就朝着根的方向上冒一步。继续该过程直到 X 能够放入空穴中为止。
如下图所示：为了插入 14，我们在堆的下一个可用位置上建立一个空穴，由于将 14 插入空穴破坏了堆序性质，因此将 31 移入该空穴。
在图中，将元素从做到右执行插入，所以下一个空穴的位置应该在 31 的右节点上。
deleteMin（删除最小元）
当删除一个最小元是，要在根节点建立一个空穴。由于现在少了一个元素，因此堆中最后一个元素 X 必须移动带该堆的某个地方。<u>这是为了满足二叉堆的结构性质 -- 它是一棵完全二叉树，空穴只能在最后一层的最后一个元素之后</u>
因此，我们将空穴的两个儿子中较小者移入空穴这样就把空穴向下推了一层。
重复该步骤直到 X 可以被放入空穴中。
例如，对于下面的例子中，我们先删除元素 13，这将在二叉堆的根节点上建立一个空穴。随后往里面插入数字 31.
在堆的实现中经常发生的错误是当堆中存在偶数个元素的时候，可能会遇到某个节点只有一个子节点的情况（只会在最下层出现）。
package com.mosby.ch06;
/**
* @author dhy
*/
public class BinaryHeap <T extends Comparable<? super T>> {
public BinaryHeap(){
this(DEFAULT_CAPACITY);
}
public BinaryHeap(int capacity){
currentSize = 0;
array = new Comparable[capacity];
}
/**
* 向堆插入一个元素<br><br>
*
* <blockquote>
*
* 在这里我们的代码使用了一个小技巧：我们现在的目的是要将当前堆中的空穴（初始为数组中最后一个元素之后）
* 移动到一个满足将 X 插入该空穴后不影响堆的性质的位置。<br><br>
*
* 如果我们每次都将当前空穴的位置和它的父元素交换，那么对于一个元素上滤 d 层，
* 那么由于交换而执行的赋值次数就是 3d。<br><br>
*
* 而这里，我们每次只是在满足条件时将父节点的值赋给了这个空穴而没有将空穴的值上滤。<br>
* 这样上滤 d 层将只需要 d 次对空穴的赋值和一次最后将 X 插入的赋值。总共 d+1 次赋值。
*
* </blockquote>
*
* @param x
*/
public void insert(T x){
//因为堆内部的数组实现的第一个元素是空
if(currentSize == array.length - 1){
enlargeArray(array.length * 2 + 1);
}
//当前空穴的位置在最后一个元素的后一位，同时插入空穴之后 currentSize 增加一。等同于下面的代码
//int hole = currentSize + 1;
//currentSize++;
int hole = ++currentSize;
for(; hole > 1 && x.compareTo((T) array[hole / 2]) < 0; hole /= 2){
array[hole] = array[hole / 2];
}
array[hole] = x;
}
public T findMin(){
if(isEmpty()){
return null;
}
return (T) array[1];
}
public T deleteMin(){
if(isEmpty()){
throw new RuntimeException("Under flow");
}
T minItem = findMin();
array[1] = array[currentSize--];
percolateDown(1);
return minItem;
}
public boolean isEmpty(){
return currentSize == 0;
}
public void makeEmpty(){
currentSize = 0;
}
private static final int DEFAULT_CAPACITY = 100;
private int currentSize;//当前堆中元素个数
private Comparable<? super T>[] array;//堆内部的以数组的形式存放
/**
* 对空穴进行下滤
* @param hole
*/
private void percolateDown(int hole){
//这里 child 的初值不会影响程序的正确性，但是 eclipse 的编译器有 bug， int child; 是无法通过编译的
//在 IDEA 下可以直接 int child;
int child = hole * 2;
Comparable<? super T> tmp = array[hole];
/**
* 这里注意一点，hole * 2 <= currentSize，因为数组的第一个元素为空<br>
* 数组中的实际元素应该是 array[i] - array[currentSize]
*/
for(; hole * 2 <= currentSize; hole = child){
child = hole * 2;
/**
* 在下滤的过程中，我们每次将当前节点的两个子节点中较小的那个子节点跟空穴交换<br>
*
* 但是这必须要考虑一个问题，在最下层的时候，可能会有某个节点只有一个子节点<br>
*
* 而在非最下层则不会有这个问题，因为二叉堆是一个完全二叉树。<br>
*
* 而根据二叉堆的插入性质（从左往右插入），那么只有一个元素的节点，这个元素的子节点肯定
* 就是二叉堆的最后一个节点。此时 hole == currentSize.
*/
if(child != currentSize && array[child + 1].compareTo((T) array[child]) < 0){
child++;
}
if(array[child].compareTo((T) tmp) < 0){
array[hole] = array[child];
}else{
break;
}
}
array[hole] = tmp;
}
/**
* 如果提供了通过数组初始化二叉堆的方式，那么在传入一个数组后调用该方法即可得到一个二叉堆。
*/
private void buildHeap(){
for(int i = currentSize / 2; i > 0; i--){
percolateDown(i);
}
}
public void enlargeArray(int newSize){
Comparable[] newArray = new Comparable[newSize];
for(int i = 1; i <= currentSize; i++){
newArray[i] = array[i];
}
array = newArray;
}
public int size(){
return currentSize;
}
}左式堆
设计一种堆结构像二叉堆那样有效的支持合并操作（即以 O(N) 时间处理一个 merge）而且只使用一个数组似乎很困难。原因在于，合并似乎需要把一个数组拷贝到另外一个数组中去。
<u>正因为如此，所有支持有效合并的高级数据结构都需要使用链式数据结构</u>
左式堆 （leftist heap）像二叉堆一样具有结构性和有序性。左式堆也是二叉树，左式堆和二叉堆的唯一区别是：左式堆不是理想平衡（perfectly balanced），而实际上趋向于非常不平衡。
左式堆性质
我们把任意节点 X 的零路径长（null path length） npl(X) 定义为从 X 到一个不具有两个儿子的节点的最短路径长。因此，具有 0 个或一个儿子的节点的 npl 为 0，而 npl(null) = -1。
任意节点的零路径长比它的所有儿子节点的零路径长的最小值大1.这个结论也适用于少于两个儿子的节点，因为 null 的零路径长是 -1.
左式堆的性质是：对于堆中的
每一个节点 X，左儿子的零路径长大于等于右儿子的零路径长。
实际上，对于左式堆的任意一个节点只能有三种情况，有两个子节点、没有子节点、仅有一个节点且该节点为左子节点。
也就是说，如果存在任意一个节点只有右节点，那么这个堆一定不是左式堆。但是，如果一个节点每个节点都满足上面的条件，它不一定是左式堆，还需要满足零路径长的条件。
显然，在上路中，左图是一棵左式堆；而右图则不是，因为右图的根节点的左子节点的左子节点的零路径长 == 0，而根节点的左子节点的右子节点的零路径长 == 1.
这个性质使得它不是一棵理想平衡树，因为它显然偏重于使树向左增加深度。
因为左式堆趋向于加深左路径，所以右路径应该短。事实上，沿左式堆的右路径是该堆中的最短路径。否则，就会存在某个节点 X 的左儿子的最短路径长小于右儿子的最短路径长。
node
/ \
node `node`
/ \ / \
node node `null` node例如，对于上面这个树，对于标记的 node 节点是不符合左式堆的，因为它的左子节点的零路径长是 -1，而右子节点的零路径长是 0.
左式堆的基本操作
左式堆的基本操作是合并。注意，插入只是合并的特殊性情况。
3 | 6 |
/ \ | / \ |
10 8 | 12 7 |
/ \ / | / \ / \ |
21 14 17 | 18 24 37 18 |
/ / | / |
23 26 | 33 |合并具有大的 root 的堆与具有较小的 root 的堆的右节点
函数栈最上层
| 6 |
| / \ |
8 | 12 7 |
/ | / \ / \ |
17 | 18 24 37 18 |
/ | / |
26 | 33 |函数栈的底层，该层等待上层函数的返回
3 |
/ |
10 |
/ \ |
21 14 |
/ |
23 |递归的去进行 merge 操作
函数栈最上层
8 | 7 |
/ | / \ |
17 | 37 18 |
/ | |
26 | |函数栈第二层
| 6 |
| / |
| 12 |
| / \ |
| 18 24 |
| / |
| 33 |函数栈的底层，该层等待上层函数的返回
3 |
/ |
10 |
/ \ |
21 14 |
/ |
23 |继续进行递归 merge
函数栈最上层
8 | |
/ | |
17 | 18 |
/ | |
26 | |函数栈第二层
| 7 |
| / |
| 37 |
| |
| |函数栈第三层
| 6 |
| / |
| 12 |
| / \ |
| 18 24 |
| / |
| 33 |函数栈的底层，该层等待上层函数的返回
3 |
/ |
10 |
/ \ |
21 14 |
/ |
23 |继续进行递归 merge
函数栈最上层，这个时候函数栈开始退出
null | 18 |函数栈最二层
8 | |
/ | |
17 | |
/ | |
26 | |函数栈第三层
| 7 |
| / |
| 37 |
| |
| |函数栈第四层
| 6 |
| / |
| 12 |
| / \ |
| 18 24 |
| / |
| 33 |函数栈的底层，该层等待上层函数的返回
3 |
/ |
10 |
/ \ |
21 14 |
/ |
23 |函数栈开始退出
函数栈最上层，上层函数退出，同时必须更新 root 节点的 npl
8 | |
/ \ | |
17 18 | |
/ | |
26 | |函数栈第二层
| 7 |
| / |
| 37 |
| |
| |函数栈第三层
| 6 |
| / |
| 12 |
| / \ |
| 18 24 |
| / |
| 33 |函数栈的底层，该层等待上层函数的返回
3 |
/ |
10 |
/ \ |
21 14 |
/ |
23 |函数栈继续退出，同时如果root左子树的零路径长小于右子树的零路径长则必须翻转两个子树
函数栈最上层，上层函数退出，同时必须更新 root 节点的 npl
7
/ \
8 37 | |
/ \ | |
17 18 | |
/ | |
26 | |函数栈第二层
| 6 |
| / |
| 12 |
| / \ |
| 18 24 |
| / |
| 33 |函数栈的底层，该层等待上层函数的返回
3 |
/ |
10 |
/ \ |
21 14 |
/ |
23 |最后得到的结果为 图 6-24 所示。
递归的退出条件是：
被 merge 的两个左式堆中任意一个为 null，则返回另一个；
两个左式堆中那么具有较小 root 节点的左子节点为 null 时，将具有较大 root 的节点作为具有较小 root 的节点的左子节点，并返回具有较小 root 的几点。这里隐含了一个信息：当一个左式堆的左子节点为 null 时，它的右子节点必定为 null。因为如果右子节点不为 null，那么它就不满足左式堆的条件了。
如果这两个堆中有一个为空，那么我们可以返回另外一个堆。
否则合并他们：
首先，我们递归的将具有大的 root 的堆与具有小的 root的堆的右子堆合并。我们在递归算法中需要保证递归得到的这棵树是左式堆。
为什么这里是合并较大 root 的堆和较小 root 的堆的右子堆呢？
因为，我们合并出来的这个堆需要做为原来那个堆的右子堆，而根据左式堆的性质，一个节点所有的子节点都必须大于该节点。
图 6-23 得到的不是左式堆。左式的性质在根处被破坏。
在我们步骤 1. 中得到的新的子树是左式堆，而右子树本身就是左式堆，所以这棵树是不是满足左式堆，只要左子树的零路径长大于新的右子树的零路径长即可。
如果不满足，我们只需要将左子树和右子树的节点交换并更新零路径长就可以了。
package com.mosby.ch06;
/**
* 左式堆：与普通二叉堆区别在于，左式堆不是一个完全二叉树，并且左式堆不是一个理想平衡二叉树。
*/
public class LeftistHeap <E extends Comparable<? super E>> {
public LeftistHeap(){
root = null;
}
/**
* 公有的 merge 方法将 anotherLeftistHeap 合并到控制堆中。
* 随后 anotherLeftistHeap 变成了空的。
* 在第一趟，我们通过合并两个堆的右路径建立一棵新的树。为此，以排序的方式安排 H<sub>1</sub> 和 H<sub>2</sub>
* 右路径上的节点，保持他们各自的左儿子不变。
* 第二趟构成堆，儿子的交换工作在左式堆性质被破坏的那些节点上进行。
* <br>
* @param anotherLeftistHeap 被合并的左式树
*/
public void merge(LeftistHeap<E> anotherLeftistHeap){
if(this == null){
return ;
}
root = merge(root, this.root);
anotherLeftistHeap.root = null;
}
/**
* 向左式树中插入新的元素
* <br>
* @param x
*/
public void insert(E x){
root = merge(new Node<>(x), root);
}
/**
* 寻找左式堆中最小的元素
* <br>
* @return 左式堆最小元素
*/
public E findMin(){
if(isEmpty()){
return null;
}
return root.theElement;
}
/**
* 删除左式堆中最小元素，并返回该元素
* <br>
* @return 被删除的元素
*/
public E deleteMin(){
if(isEmpty()){
return null;
}
E minItem = root.theElement;
root = merge(root.left, root.right);
return minItem;
}
/**
* 返回左式堆是否为空
* <br>
* @return
*/
public boolean isEmpty(){
return root == null;
}
/**
* 将左式堆设置为空堆
*/
public void makeEmpty(){
root = null;
}
/**
* 内部类用于表示左式堆的节点，相对于普通的二叉树多了 npl（null path length）用于记录空路径长
* <br>
* @param <E> 节点中的存储的对象
*/
private static class Node<E>{
Node(E theElement){
this(theElement, null, null);
}
Node(E theElement, Node<E> left, Node<E> right){
this.theElement = theElement;
this.left = left;
this.right = right;
npl = 0;
}
E theElement;
Node<E> left;
Node<E> right;
int npl;
}
private Node<E> root;
/**
* merge 方法被用于消除一些特殊情形并保证 H<sub>1</sub> 有较小的根。
* <br>
* @param h1
* @param h2
* @return
*/
private Node<E> merge(Node<E> h1, Node<E> h2){
if(h1 == null){
return h2;
}
if(h2 == null){
return h1;
}
if(h1.theElement.compareTo(h2.theElement) < 0){
return merge1(h1, h2);
}else{
return merge1(h2, h1);
}
}
/**
* merge1 执行实际的合并操作，并且在 merge1 的调用中，h<sub>1</sub> 小于 h<sub>2</sub>
* <br>
* @param h1
* @param h2
* @return
*/
private Node<E> merge1(Node<E> h1, Node<E> h2){
//根据左式堆的性质，如果 h1.left == null，那么 h1.right == null 也成立
if(h1.left == null){
h1.left = h2;
}else{
h1.right = merge(h1.right, h2);
if(h1.left.npl < h1.right.npl){
swapChildren(h1);
}
h1.npl = h1.right.npl + 1;
}
return h1;
}
private void swapChildren(Node<E> t){
Node<E> tmp = t.left;
t.right = t.left;
t.left = tmp;
}
}