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

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

【关键词】完全二叉树；下滑调整；堆调整；线性表操作

1.介绍

具有优先级队列[1]的数据集合在实际应用中为各种搜索带来便利。搜索是在数据集合中寻找满足某种条件的数据元素，是数据处理最常见的一种运算。对于不同方式组织起来的搜索结构，相应的搜索方法也不同。往往搜索结构的性质也影响着搜索速度。

对于以完全二叉树[1，2]结构形式存在的数据集合，在搜索前进行某种调整后，使数据集合具有堆[2，3]的性质，可以提高搜索速度。调整的方法关系到整个处理过程的效率问题。

这里借用线性表[1，3]对元素位置进行调整，再转换为原来的非线性表结构，以此取代最初的数据集合。

2.算法描述

将给定的以链表结构存取的完全二叉树转化为以数组结构存取的完全二叉树，对数组元素位置进行调整，使得该数组集合具有堆性质，最后依此数组来新建具有堆性质的完全二叉树。

算法中用到相关变量和数据结构：

Stack stack；//全局变量栈stack，用来作为中间记录载体

template

struct TreeNode//二叉树结点数据结构

3.算法思路与过程

整个调整过程分为三步。首先，完全二叉树的数组表示：将链表结构的完全二叉树转化为数组结构完全二叉树。其次，数组的堆调整[3]：对数组heap[]进行下滑调整使得数组heap[]的数据集合具有堆的性质。最后，完全二叉树的创建：依heap[]数组创建完全二叉树来替代原来的完全二叉树。图1为该调整算法分三步处理的图例。

图1 借用线性变操作流程处理

完全二叉树的数组表示：基本思想：将n个结点的完全二叉树，自顶向下，同一层次自左向右连续给结点编号0，1，2，3，......，n.，借助队列作为中间载体，然后按此编号将树中个结点顺序地放在数组heap[]中，即heap[i]为编号i的结点。图2为该操作的算法思想的流程图。

.

图2 二叉树结点元素线性表转存

数组的堆调整：依次以数组heap[]的每个元素为调整对象，使得调整后的数组heap[]满足heap[i]≤heap[2i+1]且heap[i]≤heap[2i+2]（或者heap[i]≥k[2i+1]且k[i]≥k[2i+2]）条件。调整的过程分为，对每个结点的下滑调整和整体堆化。下列代码实现某一个结点的下滑调整。同时由于在对每一个结点进行下滑调整时，他的子树都已经是调整好的具有堆性质的树，图3为从下至上，在每一个结点进行下滑调整后的操作思路。

图3 线性表大半个元素的下滑调整

任意给定堆H0和H1，以及结点p，为得到堆H3，只需要将结点R0和R1当作p的孩子，然后对p进行下滑调整。

某个结点的下滑调整的算法代码实现：

完全二叉树的创建：该操作实际是上述完全二叉树的数组表示的逆操作。即以数组heap[]中的各元素为结点来创建一个以链表表示的完全二叉树，且当给该二叉树进行自顶向下，同一层次自左向右连续编号后，编号i的结点为数组元素heap[i]。图4为该操作的算法思想的流程图。

图4 堆性质的二叉树结构转化

4.算法复杂度和测试结果

空间复杂度：该算法用到的队列和数组的空间大小之和：S（3└n/2┘），单位为sizeof（TreeNode）。

时间复杂度：在对完全二叉树元素进行数组表示时进行了n次的进栈操作，进栈操作结束后再执行了n次的出栈操作来转存到数组中，二叉树的转存操作时间复杂度为T（2n）。调用下滑调整算法时，while循环的次数最大为树的深度减1，所以数组的下滑调整算法的时间复杂度为T（log2n）。再依次操作该数组每一个元素，调用了n次数组的下滑调整算法。基于数组的堆调整算法复杂度整体的时间复杂度为T（nlog2n+2n）。

实验测试结果：

在测试实验中，每次对相同完全二叉树用两种方法进行堆调整验证，记录了算法执行时间Time下面根据记录的数据，绘制出曲线图（如图5）进行观察对比。

图5 曲线图

由图5曲线图，可以明显得出结论：随着二叉树结点数目的增多，堆调整的处理速率在增加。由于该转换过程涉及到两处组织结构的转换，导致在数据量庞大时出现延时，这也是本算法研究的最大缺点。

5.结论

本文通过以链表结构的完全二叉树为处理对象，形式地给出了借用线性表作为中间载体，再转会为完全二叉树结构。该算法在对链表结构的完全二叉树的堆调整算法时，要经过多系组织结构的转换在这样的情况下，当数据量特别大的时候肯定会出现延时情况。在后续阶段我们将对处理庞大数据量的二叉树结构进行算法研究，解决延时问题。

参考文献：

[1]Glenn W Rowe：Introduction to Data Structures and Algorithms with C++，Prentice-HallEurope（1997）.

[2][美]Mark Allen Weiss.数据结构与算法分析：Java语言描述[M].北京：人民邮电出版社（英文版第3版），2007.

[3][中]殷人昆数据结构（用面向对象方法与C++语言描述）[M].北京：清华大学出版社（第二版）.

本文属基于青海大学2012年课程建设项目（KC-12-2-3）“数据结构与算法青海大学教育教学研究项目”。

作者简介：胡媛，女，现就读于青海大学计算机科学与技术系，研究方向：计算机技术与应用。