【华科复试】【贪心算法】最优二路归并树&二路归并排序

二路归并模式:每次仅作两个文件的归并;当有多个文件时,采用两两归并的模式,最终得到一个完整的记录文件。 二元归并树:二路归并模式的归并过程可以用一个二元树的形式描述,称之为二元归并树。 贪心求解: 任意两个文件的归并所需的元素移动次数与这两个文件的长度之和成正比。度量规则:每次选择需要移动次数最少的两个集合进行归并。处理规则:每次选择长度最小的两个文件进行归并。 为得到归并树根结点表示的归并文件,外部结点中每个文件记录需要移动的次数=该外部结点到根的距离,即根到该外部结点路径的长度,如:下列F4在整个归并过程中的移动量为4。 带权外部路径长度:记di是由根到代表文件Fi的外部结点的距离,q