数据结构考研分类复习真题 第十章 答案[42]

()加入后

()加入后

()[题目分析]从插入位置进行调整调整过程由下到上首先根据元素个数求出插入元素所在层次数以确定其插入层是最大层还是最小层若插入元素在最大层则先比较插入元素是否比双亲小如是则先交换之后将小堆与祖先调堆直到满足小堆定义或到达根结点若插入元素不小于双亲则调大堆直到满足大堆定义若插入结点在最小层则先比较插入元素是否比双亲大如是则先交换之后将大堆与祖先调堆若插入结点在最小层且小于双亲则将小堆与祖先调堆直到满足小堆定义或到达根结点

()void MinMaxHeapIns(RecType R[]int n)

{ //假设R[n]是最小最大堆插入第n个元素把R[n]调成最小最大堆

j=n; R[]=R[j];

h=ëlognû+; //求高度

if (h%==) //插入元素在偶数层是最大层

{i=n/;

if (R[]key<R[i]key) //插入元素小于双亲先与双亲交换然后调小堆

{R[j]=R[i];

j=i/;

while (j> && R[j]>R[i]) //调小堆

{R[i]=R[j]; i=j; j=i/; }

R[i]=R[];

}

else //插入元素大于双亲调大堆

{i=n; j=i/;

while (j> && R[j]<R[i])

{R[i]=R[j]; i=j; j=i/; }

R[i]=R[];

}

}

else //插入元素在奇数层是最小层

{i=n/;

if (R[]key>R[i]key) //插入元素大于双亲先与双亲交换然后调大堆

{R[j]=R[i];

j=i/;

while (j> && R[j]<R[i]) //调大堆

{R[i]=R[j]; i=j; j=i/; }

R[i]=R[];

}

else //插入元素小于双亲调小堆

{i=n; j=i/;

while (j> && R[j]>R[i])

{R[i]=R[j]; i=j; j=i/; }

R[i]=R[];

}

}

}//MinMaxHeapIns

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []