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

[题目分析]根据定义DEAP是一棵完全二叉树树根不包含元素其左子树是一小堆(MINHEAP下称小堆)其右子树是一大堆(MAXHEAP下称大堆)故左右子树可分别用一维数组l[]和r[]存储用m和n分别表示当前两完全二叉树的结点数左右子树的高度差至多为且左子树的高度始终大于等于右子树的高度

我们再分析插入情况当均为空二叉树或满二叉树(m=h)时应在小堆插入小堆满(二叉树)后在大堆插入即当m>=n且m<>h且ëlogmûëlognû<=在小堆插入否则在大堆插入

最后分析调堆情况在小堆m处插入结点x后若x的值不大于大堆的m/结点的值则在小堆调堆否则结点x与大堆的m/结点交换然后进行大堆调堆在大堆n处插入结点x后若x不小于小堆的n结点则在大堆调堆否则结点x与小堆的n结点交换然后进行小堆调堆

在DEAP中插入结点后的结果如图

先插入到大堆因为小于小堆中对应位置的所以和交换交换后只需调整小堆从叶子到根结点这时大堆不需调整因为插入小堆时要求必须小于对应大堆双亲位置的否则要进行交换

void InsertDEAP(int l[]r[]mnx)

//在DEAP中插入元素xl[]是小堆r[]是大堆m和n分别是两堆的元素个数x是待插入元素

{if (m>=n && m<>h && ëlogmûëlognû<=)// 在小堆插入xh是二叉树的高度

{m++; //m增

if (x>r[m/]) //若x大于大堆中相应结点的双亲则进行交换

{l[m]=r[m/];

c=m/; f=c/;

while (f> && r[f]<x) //调大堆

{r[c]=r[f]; c=f; f=c/;}

r[c]=x;

} //结束调大堆

else //调小堆

{c=m; f=c/;

while (f> && l[f]>x)

{l[c]=l[f]; c=f; f=c/;}

l[c]=x;

}

else //在大堆插入x

{n++; //n增

if (x<l[n]) //若x小于小堆中相应结点则进行交换

{r[n]=l[n];

c=n; f=c/;

while (f> && l[f]>x) //调小堆

{l[c]=l[f]; c=f; f=c/;}

l[c]=x;

} //结束调小堆

else //调大堆

{c=n; f=c/;

while (f> && r[f]<x)

{r[c]=r[f]; c=f; f=c/;}

r[c]=x;

}

}//结束InsertDEAP算法

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