數據結構考研分類復習真題 第十章 答案[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算法

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23171.html