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

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

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