一种基于递归堆调整方法的最小生成树求解算法

Sollin算法是一种非常适合于并行计算的求解最小生成树方法,但其较高时间复杂度抵消了并行计算带来的好处。本文提出了一种递归的堆调整实现方法以及堆合并原则,解决了Sollin算法在子树合并时快速找到连接两棵相邻子树的最短的边的问题,降低最小生成树求解的时间复杂度。理论分析表明,该改进方法有效地将Sollin算法的时间复杂度由O(n2log2n)降低到了O(elog2n)。同时,根据边权重的分布情况不同,该算法并非必须遍历所有的边才能得到MST,实际时间复杂度将优于O(elog2n),最优可达O(n(log2n)2)。

借用线性表调整的二叉树堆转换算法

在很多应用中，需要对完全二又树结点位置进行调整，使该数据集合具有堆的性质。现经过实验提出一种改进算法，利用优先级队列颇似队列（删除最早的数据）和栈（删除最新的数据）特性转存二叉树结构的结点元素，存储在线性表中。直接调用下滑调整算法操作线性表，使之具有堆特性，后续转回二叉树。