论文导读：由于左倾堆能够高效的实现两个左倾堆的合并，因此左倾堆又被称为可合并的堆，目前对左倾堆的操作也大都是基于对左倾堆的合并操作的。本文提出了一个生成所有左倾堆的算法，算法涉及了很多有关左倾堆的操作，为深入研究左倾堆的结构和性质提供了有力的支持。根据左倾堆的性质提出了一种生成所有左倾堆的算法,算法涉及了有关左倾堆的操作，使用了链队列和链栈，并对算法的时间复杂度进行了详细的分析。
关键词：生成，左倾堆，算法
1引言
左倾堆(leftist heap)是1972年C.A.Crane提出的，左倾堆是一种优先队列的实现，它的节点除了和二叉树的节点一样具有左右子树指针外还有两个属性：键值和距离。距离是如下定义的：
一个具有空左子树或空右子树的节点称为外节点，一个节点的距离是这个节点到最近的外节点所经过的边的数目（最近的意思是边的数目最小），特别的，如果一个节点本身是外节点，则它的距离为0，而空节点的距离为-1。
一颗二叉树要成为一个左倾堆需要满足两条性质：
1.一个节点的键值小于或等于它的左右子节点的键值；
2.一个节点的左子节点的距离大于或等于右子节点的距离，这就是结构的左倾性。
由于左倾堆能够高效的实现两个左倾堆的合并，因此左倾堆又被称为可合并的堆，目前对左倾堆的操作也大都是基于对左倾堆的合并操作的。本文提出了一个生成所有左倾堆的算法，算法涉及了很多有关左倾堆的操作，为深入研究左倾堆的结构和性质提供了有力的支持。论文参考网。
2 算法思路和描述
2.1算法的数据结构和变量说明
（1）左倾堆节点的结构
key表示节点的键值，lc指向左孩子,rc指向右孩子, p指向父结点,d该节点的距离,ld左子节点的距离,rd右子节点的距离，ct表示该节点是父节点的左孩子还是右孩子，还是它本身就是父节点。
(2)链队列和链栈元素节点
addr是指针域，指向左倾堆的根节点,
link指向下一个出链队列或下一个出链栈的元素节点。
(3)mkey[]存放按节点键值非递增序排列的键值的数组。论文参考网。
(4)lftree[]存放左倾堆节点的数组
(5)int count1,count2,insertindex,num假如当前左倾堆的节点数目是m,要生成m+1个结点的左倾堆，count1表示队列中节点数目是m的左倾堆的数目，count2表示队列中节点数目是m+1的左倾堆的数目，insertindex表示当前要插入到左倾堆的节点的索引，num当前生成的左倾堆的数目。
定义1：左倾堆中的某个节点如果在插入左孩子或右孩子时仍然满足是一个左倾堆，称这样的节点为左倾堆的可插入节点。
左倾堆的任意节点nd是否是一个可插入节点的判断：如果nd可以插入孩子那么首先它是一个外节点，即要不它是一个叶子节点，要不它只有左孩子而没有右孩子。
如果该节点是叶子节点，插入左孩子不会对左倾堆的性质有所改变,nd是可插入节点；
如果nd有左孩子没有右孩子，由于插入右孩子会影响父节点及祖先节点的距离，需要向上回溯才能判断插入后是否仍然满足左倾堆的性质。那么回溯什么时候终止呢，假如回溯到节点g,如果g不是根节点，首先判断是否满足g的左子节点的距离否大于右子节点的距离，如果不满足，那么nd插入右孩子后，g的右子节点距离将大于左子节点距离，nd不是可插入节点；如果满足，需要考虑两种情况，一种情况g本身是右孩子，需继续回溯，另一种情况g本身是左孩子，这种情况下nd是可插入节点。如果g是根节点且g的左子节点的距离大于右子节点的距离，nd是可插入节点，否则nd不是一个可插入节点。论文参考网。
判断出一个节点是可插入节点，如何为其插入孩子呢，原有的左倾堆还要判断其他节点是否是可插入节点，因此插入操作不能在原有左倾堆上进行，需要复制左倾堆和可插入节点的位置，在复制的左倾堆上进行插入操作。为可插入节点插入左孩子，需要修改左孩子的p域和ct域以及可插入节点的ld域。插入右孩子同样也要向上回溯，并改变相应的一些域的值，如果插入右孩子后，可插入节点的ld和rd相等，需要将新生成的左倾堆进行复制，并将可插入节点的左右子树交换，同时生成两个左倾堆。
算法的总体思路是：假设要生成具有N个节点的所有的左倾堆，采用构造法，即从一个节点的左倾堆逐步构造出具有N个节点的所有左倾堆的方法。先让有一个节点的左倾堆入队列，当有一个节点的左倾堆出队列时，添加一个节点后将生成一个两个节点的左倾堆，并插入队列。同样当一个有m（1≤m≤N-1）个节点的左倾堆出队列时，遍历这个左倾堆的每个节点，判断这个节点是否是可插入节点，如果是就将孩子插入到可插入节点，这样将生成一个或两个有m+1个节点的新的左倾堆，并插入队列。当所有具有N-1个节点的左倾堆都出队列时，我们也同时就生成了所有具有N个节点的左倾堆。当具有N个节点的左倾堆出队列时，我们就打印这个左倾堆，当队列为空时，所有的有N个节点的左倾堆就打印完毕了
2.3算法过程
(1)初始化：
将N个键值从小到大排序，依次存放在mkey[1]……mkey[N]中，令i=1，如果i≤N,lftree[i].key=i;lftree[i].lc=NULL;
lftree[i].rc=NULL;lftree[i].p=NULL;
lftree[i].d=0;lftree[i].rd=-1;
lftree[i].ld=-1;lftree[i].ct=-1;
如果i>N，lftree[1]进队列,count1=1;count2=0;insertindex=2;num=0；
(2)如果队列不为空,转(3)，否则算法结束；
(3)队列元素q出队列，如果insertindex=N+1,则num=num+1,打印第num个左倾堆q->addr,转(2).否则转（4）；
(4)count1=count1-1;中序遍历q->addr并判断遍历的节点是否是可插入节点，如果是可插入节点则为其插入孩子，并将新生成的左倾堆入队列，count2=count2+1；
(5)如果count1=0,那么count1=count2，count2=0,insertindex=inserindex+1;,说明insertindex个节点的左倾堆已经生成完毕。转（2）。
1/2 1 2 下一页 尾页 |
