已知由n—1个关键字组成的序列(K1,K2,…,Kn—1)是大顶堆,现在增加一个关键字Kn,要求将关键字序列(K1,K2,…,Kn—1,Kn),重新调整为大顶堆。请完成以下要求: 根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。

admin2017-04-28  52

问题 已知由n—1个关键字组成的序列(K1,K2,…,Kn—1)是大顶堆,现在增加一个关键字Kn,要求将关键字序列(K1,K2,…,Kn—1,Kn),重新调整为大顶堆。请完成以下要求:
根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。

选项

答案算法实现如下: #define n 100; //宏定义n常量,由用户自定义结点个数 int K[n]; //关键字序列 void heap() { int i=n/2; //找到最后一个结点的父母结点 if(n%2==1) //当n是右结点时 { if (K[i] <K[n—1] &&K fn—ll >K fnl)swap(K[n—1] ,K [i]);//swap()实现交换两个元素 if (K[i]<K[n]&&K[n—l] <K [n)) swap(K[nl ,K [i]); } else //当n是左结点 { if(K[主]<K[n])swap(K[n],K[i]); } i=1/2; while (i>0) //依次向上调整 if {K [i] <K [n—1] &&K [n—1] >K [n] ) swap (K [n—1] ,K [i]) ; if (K [j] <K [n]& &K [n—1] <K [n] ) swap (K [n] ,K [i]) ; i=1/2; } }

解析
转载请注明原文地址:https://jikaoti.com/ti/enfjFFFM
0

最新回复(0)