6.3二叉堆
优先队列至少两种操作：插入insert等同于入队enqueue、删除最小者deleteMin等同于出队dequeue。
优先队列可以用于外部排序和贪婪算法的实现。
优先队列实现在第一种方法（简单）是在表头以O（1）时间执行插入操作，O（N）时间遍历链表删除最小元。或始终使链表处于排序状态，则insert代价O（N）,deleteMin代价O（1）。
优先队列的第二种实现方法二叉查找树，insert和deleteMin都是O(lgn)。而查找树有许多不需要的类方法。
优先队列的第二种实现方法是使用（数据）二叉堆实现，不需要链且遍历简单，以O(logN)支持上两种操作。
堆具有结构性和堆序性两种性质。结构性指堆是完全二叉树（而叶子也满的是理想二叉树)。堆序性质指任意节点小于它的后裔。
数组保存二叉堆，根元素从索引1开始（索引0存值-1）。数据实现的二叉堆的任一位置i，左儿子2i，右儿子2i+1，父亲i/2的下取整。
//**********
二叉堆的API：空容项3种构造方法、堆一般方法、和3个内部实现方法：扩容、建堆、上下滤。构造函数创建的是无序堆，建堆函数用于维护堆序。
public classBinaryHeap> {
private static final int DEFAULT_CAPACITY = 10;
private int currentSize;
private AnyType[] array;
public BinaryHeap() {}
public BinaryHeap(int capacity) {}
public BinaryHeap(AnyType[] items) {}
public void insert(AnyType x) {}
public AnyType findMin() {}
public AnyType deleteMin() {}
public boolean isEmpty() {}
public void makeEmpty() {}
private void percolateDown(int hole) {}
private void buildHeap() {}
private void enlargeArray(int newSize) {}
}
// **********
新元素中堆中上滤percolate up，直到找到正确的位置。
上滤操作为：由插入位置向父延伸的插入排序。三步：抽牌、大牌下沉、放牌。
数组二叉堆的插入INSERT复杂度O（logN）。业已证明，执行一次插入平均需要2.607次比较，平均操作上移1.607层。
//**********
public void insert(AnyType x)
{
if(currentSize == array.length-1)
enlargeArray(array.length*2+1);
//Percolate up
int hole = ++currentSize;
for(;hole>1&&array[hole/2].compareTo(x)>0;hole/=2)
array[hole]=array[hole/2];
array[hole]=x;
}
//**********
优先队列的弹堆操作deleteMin：取根元素用于返回、最大元素补到根元素、再下滤。
下滤percolateDown操作：为向子延伸的插入排序。三步：抽牌、小牌小浮、放牌。注意浮牌的左儿子不出界为终止条件，原则选小儿子，右儿子小选右儿子。下滤操作的关键在于儿子选取。
上滤和下滤操作共同保证了堆序。
//**********
public AnyType deleteMin( ){
if(isEmpty())
throw new UnderflowException();
AnyType minItem=array[1];
array[1]=array[currentSize--];
percolateDown(1);
return minItem;
}
percolateDown(hole){
int child;
AnyType eject=array[hole];
for(;hole*2
child=hole*2;
if(child!=currentSize&&array[child].compareTo(array[child+1])>0)
child++;
if(array[child].compareTo(eject)<0)
array[hole]=array[child];
else
break;
}
array[hole]=eject;
}
//**********
堆的其它操作--
行数据被封闭在类中，通过compareTo()比较关键字的值。降低关键字decreaseKey的值要上滤，增加关键字increaseKey的值要下滤。降低关键字的值可以用于提高程序的优先级。
删除delete为：将关键字置无穷，再下滤，array[currentSize]=NULL,currentSize--。
建堆buildHeap就是对非叶节点下滤。
//**********
public BinaryHeap( AnyType [ ]items ){
currentSize=items.length;
array=(AnyType[])new Comparable[(currentSize+2)*11/10];//数组留有10%的容量
int i=1;
for(AnyType item:items)
array[i++]=item;
buildHeap();
}
private void buildHeap(){
for(int i=currentSize/2;i>0;i--)
percolateDown(i);
}
//**********
理想二叉树是满叶的完全二叉树。高为h的理想二叉树，节点数2^(h+1)-1，节点高度和2^(h+1)-1-(h+1)。即理想二叉树高度和为：节点数-节点数的二进制表示法的1个数。
6.4优先队列的应用
选择问题：输入是N个元素以及一个整数k，找出第k个最大元素。
选择问题方法1：将元素读入数组并排序，返回第k个最大元素，复杂度O(N^2)。
方法2:将k个元素读入数组并排序，将其余元素放入数组中的正确位置，复杂度O(N*k),若k=N/2的上取整则复杂度为O(N^2)。
选择问题更高效的优先队列解决方法3：用O(N)时间buildHeap，O(logN)时间deleteMin共k次。算法复杂度O(N+klogN)。如果k=N并在元素离开堆时记录它们的值，相当于以O(NlogN)排序，即堆排序算法。
方法4：思路同方法3而使用堆代替数组。建堆O(k),处理其余元素（N-k）*O(logk),总复杂度O(Nlogk)。
其它方法：第7章的平均时间O(N)的方法，第10章的最坏时间O(N)的方法。
排队问题：顾客到达并排队直到k个出纳员服务，求顾客平均等待多久或所排队伍多长的统计问题。
方法：顾客等待的队伍实现为一个队列。每个时钟单位走到下一个事件时间。下一个事件要么是输入文件中下一顾客到达（插入insert），要么是顾客在一位出纳员处离开（弹堆deleteMin）。由于"事件将要发生的时间"（关键字）是可达的，只需要找出最近"将来发生事件"并处理这个事件。
6.5 d-堆
d堆的插入insert运行时间O(logd,N)。d堆的deleteMin需要找到d个儿子的最小者，deleteMin复杂度O(dlogd,N)。d为2的幂，这样才能通过移动二进制实现除法，大大减少运行时间。
d堆适用于insert次数远小于deleteMin次数的算法，也适用于队列太大而不能完全装入主存的情况（功能与B树相同）。
d堆的缺点是不能find()、堆合并merge困难。
6.6左式堆
左式堆具有二叉堆基本的堆结构性和堆序性，左式堆也是二叉树。
零路径长（npl null path length）定义为不具有两个节点的最短路径长。少于两个儿子的节点npl=0，null节点的npl=-1。
左式堆性质1：左儿子npl大于等于右儿子npl。左式堆是不平衡树，偏重于向左树增加深度。
左式堆性质2：节点npl比其儿子的npl的最小值大1。
左式堆其它：右路径有r个节点的左式堆必然至少有2^r-1个节点。
左式堆节点的数据结构为：数据、左右引用、零路径长。节点要声明为privatestatic以使对象内有效。左式堆不用存元素数currentSize。
//**********
左式堆API：
public classLeftistHeap>{
private Node root;
private static class Node{
AnyType element;
Node left;
Node right;
int npl;
Node(AnyType theElement){
element=theElement;left=null;right=null;npl=0;
}
Node(AnyTypetheElement,Node lt,Node rt){
element=theElement;left=lt;right=rt;npl=0;
}
}
private void swapChildren(Node t){}
private Nodemerge(Node h1,Node h2){}
private Nodemerge(Node h1,Node h2){}
public LeftistHeap(){root=null;}
public void insert(AnyType x){}
public AnyType findMin(){}
public AnyType deleteMin(){}
public boolean isEmpty(){return root==null;}
public void makeEmpty(){root=null;}
public void merge(LeftistHeap rhs){}
}
//**********
习惯将根元素较小的参数作为第一参数。
因而合并堆函数有3个，1个合并其它堆、1个处理参数为空堆（递归底）并将"小根堆"作为第一参数、1个为堆合并算法。
左式堆合并算法为：递归地使1参右子树与2参合并,并维护2个左式堆性质，递归底为1参单节点、1参空堆。
左式堆insert显然可以用左式堆merge实现。左式堆deleteMin为合并两个子树的堆，相比于二叉堆的最大元素"先置顶"再"下滤"。左式堆均以O(logN)支持merge/insert/deleteMin。
左式堆使用“链式的二叉堆建堆”实现。buildHeap的效果可以用递归地建立左右子树然后将根下滤得到。复杂度O(N)。未实现？？？
注意以下左式堆的实现中，用根节点表示左式堆，而非使用对象名来实现算法。
//**********
左式堆merge的基本情形：
private Nodemerge(Node h1,Node h2){
if(h1==null){
return h2;
}
if(h2==null){
return h1;
}
if(h1.element.compareTo(h2.element)<0){
return merge1(h1,h2);
}else{
return merge(h2,h1);
}
}
左式堆merge的一般情形：
privatemerge1(Node h1,Node h2){
if(h1.leftChild=null){
h1.rightChild=h2;
}else{
h1=merge(h1.rightChild,h2);
if(h1.leftChild.npl
swapChildren(h1);
h1.npl=h1.rightChild.npl;
}
return h1;
}
左式堆insert算法：
public void insert(AnyType x){
merge(new Node(x),root);
}
左式堆deleteMin算法：
public NodedeleteMin(AnyType x){
AnyType minItem=root.element;
root=merge(root.leftChild,root.rightChild);
return minItem;
}
//**********
6.7斜堆
斜堆是左式堆的自调节形式，类似于伸展树和AVL树的关系。斜堆具有堆序，而无结构限制。略。
6.8二项队列（二项队列不记代码，只要能读懂即可）
二项队列的merge/insert/deleteMin的最坏运行时间O(logN),而insert平均花费O(N)。
二项队列是保证堆序的树的集合，高度为k的树恰有2^k个节点。
二项队列的buildHeap算法:？？可以先用插入代替
二项队列的merge算法:合并树操作是更新currentSize的。
二项队列的insert算法：就是合并。
二项队列的deleteMin算法：找到具有最小根的堆Bk，二项队列除去Bk形成堆集H'，Bk除去根形成堆集H'，'合并H'和H''。前3步用时O(logN)，最后一步用时O(logN)。
二项队列只能用对象名表示，而不能像二叉堆、左式堆那样用根点表示堆了。
//**********
二项队列是多叉树，节点使用左儿子右兄弟表示法。数据为节点数组theTrees和节点数currentSize。
二项队列的API：
public classBinomiaQueue>{
public static class Node{
AnyType element;
Node leftChild;
Node nextSibling;
Node(AnyType theElement){
element=theElement;leftChild=null;nextSibling=null;
}
Node(AnyType theElement,Nodelc,Node ns){
element=theElement;leftChild=lc;nextSibling=ns;
}
}
private static final int DEFAULT_TREES=1;
private int currentSize;
private Node[] theTrees;
private void combineTrees(Nodet1,Node t2){}
private void expandTrees(int newNumTrees){}
private int capacity(){}
private int findMinIndex(){}
public BinomiaQueue(){}
public BinomiaQueue(AnyType item){}
public void merge(BinomiaQueuerhs){};//二项队列的合并只实现了一个单项合并
public void insert(AnyType x){merge(newBinomiaQueue(x));}
public AnyType deleteMin(){}
public boolean isEmpty(){return currentSize==0;}
public void makeEmpty(){}
}
combineTrees的实现算法：使大根堆成为小根堆的左孩子。二项队列的优点在于它的堆合并算法简单。由于二项队列的堆的左孩子、右兄弟是单链表，因而combineTrees只需要修改t1的左孩子和t2的右兄弟。
private NodecombineTrees(Node t1,Node t2){
if(t1.element.compareTo(t2.element)>0)
return combineTrees(t2,t1);
t2.nextSibling=t1.leftChild;
t1.leftChild=t1;
return t1;
}
二项队列merge算法：
public void merge(BinomiaQueuerhs){
if(this==rhs)//Avoid aliasing problems
return;
currentSize+=rhs.currentSize;
if(currentSize>capacity()){
intmaxLength=Math.max(theTrees.length,rhs.theTrees.length);
expandTheTrees(maxLength+1);
}
Node carry=null;
for(int i=0;j=1;j<=currentSize;i++,j*=2){
Nodet1=theTrees[i];
Nodet2=i
int whichCase=t1==null?0:1;
whichCase+=t2==null?0:4;
switch(whichCase){
case 0://no trees
case 1://only this
break;
case 2://only rhs
theTrees[i]=t2;
rhs.theTrees[i]=null;
break;
case 3://this and rhs
carry=combineTrees(t1,t2);
theTrees[i]=rhs.theTrees[i]=null;
break;
case 4://only carry
theTrees[i]=carry;
carry=null;
case 5://this and carry
carry=combineTrees(t1.carry);
theTrees[i]=null;
break;
case 6://rhs and carry
carry=combineTrees(t2.carry);
rhs.theTrees[i]=null;
break;
case 7://all trees
theTrees[i]=carry;
carry=combineTrees(t1,t2);
rhs.theTrees[i]=null;
break;
}
}
for(int k=0;k
rhs.theTrees[k]=null;
rhs.currentSize=0;
}
二项队列的去头子树的堆组，由于需要将根节点的右兄弟赋空，简单的方法是用计数的循还方式（不用链）。
二项队列的deleteMin算法：
public AnyType deleteMin(){
if(isEmpty())
throw newUnderflowException();
int minIndex=findMinIndex();
AnyTypeminItem=theTrees[minIndex].element;
NodedeletedTree=theTrees[minIndex].leftChild;
//construct H''
BinomiaQueuedeletedQueue=new BinomiaQueue();
deletedQueue.expandTheTrees(minIndex+1);
deletedQueue.currentSize=(1<
for(intj=minIndex-1;j>=0;j--){
deletedQueue.theTrees[j]=deletedTree;
deletedTree=deletedTree.nextSibling;
deletedQueue.theTrees[j].nextSibling=null;
}
//construct H'
theTrees[minIndex]=null;
currentSize-=deletedQueue.currentSize+1;
merge(deletedQueue);
}
//**********
&6.9标准库的优先队列
复习栈和队列的API：
[if !supportLists]l [endif]链表ArrayLIst增add()、删remove()、改set()、查get()、判空isEmpty()/size()
[if !supportLists]l [endif]栈Stack 压栈push(AnyType x)、弹栈pop()、栈空isEmpty()
[if !supportLists]l [endif]队列Queue由LinkedList实现，入队offer()、出队pull()、element()只返头部元素不出队。
ArrayBlockingQueue队列构造需指定容量
PriorityBlockingQueue基于堆数据结构对priorityQueue进行再次包装。
DelayQueue只有延迟期满的元素才能取出。队中元素都没满，则pull返回null。
Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素，使用element()或者peek()方法
[if !supportLists]l [endif]优先队列PriorityBlockingQueue类方法：isEmpty()、offer()、poll()、toArray()。优先队列需要将队列元素implementsComparable。
[if !supportLists]l [endif]索引优先队列(TreeMap)不必实现队列元素的Comparable接口，使用更方便。索引优队典型应用于Dijstra算法。
[if !supportLists]Ø [endif]HashMap只能实现键值查找的映射关系，只有"判长空置空添删容遍"功能(size/isEmpty/clear/put/remove/containsKey/conntainsValue/get/entrySet/keySet/values)
[if !supportLists]Ø [endif]而TreeMap实现了映射和优队功能：入队put、弹队pollFirstEntry/pollLastEntry、查firstEntry/lastEntry/ceilingEntry/floorEntry/higherEntry/lowerEntry/将Entry换成Key。
注意TreeMap的遍历用Map.Entry不存在TreeMap.Entry。
[if !supportLists]Ø [endif]TreeMap具有很强大查键功能，却不具有改键功能只能先remove后put。
