数据结构与算法数据结构.pdf

高等数据结构与算法
图1 最小-最大堆
a. 我们如何找到最小元和最大元？
b. 给出一个算法将一个新节点插入到该最小-最大堆中。
答：（a）最小元即为根节点 A，最大元即为 A 的左右孩子中的较大值；
（b）假设插入节点为 t,此堆的根节点记为 P，其中 P->next 表示 P 的
孩子，P->data 表示节点 P 所储存的值。
算法：t 自根节点向下合并，每一次与节点比较后，从新赋值的 t 向右路径继续向下合并，直到其不
再遇到节点为止（即最终的 t 成为叶子节点）。
（1） t=max{t,P->data }，此时 P->data= min{t, P->data },P=P->next;
（2） t=min{t, P->data }，此时 P->data= max{t, P->data },P=p->next;
（3） 顺序重复上面两个步骤，当 P=NULL，将 t=P->data,结束。
答：左式堆的任意节点作为根节点都是左式堆，合并的时候以右路径为突破口，尽量不破坏左部的良好特
性。
基本方法：（1 ）将合并堆的两根节点进行比较，较大的与较小根结点的右孩子合并。
1
（2）较小堆的右分支与先前合并进来的堆仍然是两个左式堆，递归调用（1）直到输出
结果（在这里，当所比较的根节点中较小的如果没有右孩子，其较大的根节点带着堆
就充当了较小根节点的右分支，递归结束）。
输出结果：
答：问题相当于“给出某一数组，其中仅含有 0，1 ，2 三种元素，请按升序排列”这一问题。现设此数组
为 a[n];
算法： i=0：n-1，逐一检查 a[i],当其为 0 时，i++;当其不为 0 时，令 j=i,从 j=i+1:n 中找到第一个零元
a[x],利用中间变量 t 将 a[x]与 a[i]交换顺序，并记下此时的 j 值，同时退出小循环。
i 值，直到所有的零元被安放在数组的前部；
i’,此时和前面的方式一样，只不过其条件改为是否为 1 ，从而将后
面的数组也能够排列好。
算法复杂度分析：大循环中虽然嵌套了小循环，但由于小循环 j 值起点为上次循环终止的后继，终点为找
到所需 0 元的下标+1（实际上就是下一次小循环的起点），故而实际上其算法复杂度应为