配对堆定义配对堆是由子女右兄弟表示法表示的有根树该有根树满足堆序。配对堆的每一个节点由datapreright_sibling和first_child组成,data存放关键字,当节点是左边相邻节点的右兄弟时pre指向左边相邻节点。如果节点是其父节点的所有子节点最靠左的节点,则pre指向父节点。如果节点有右侧相邻节点则right_sibling指向该节点否则为空指针first_child指向当前节点的所有子节点中最靠左的节点如果没有子节点则为空配对堆操作**插入:**新建一个包含插入关键码的单节点配对堆,将该节点和当前配对堆合并**关键字减值:**把当前节点关键字修改为减少后的值,如果当前节点不是根节点则从当前节点父节点切除以当前节点为根的子树,将该子树和切除后的配对堆合并**移除最小值:**从当前配对堆中切除根节点返回根节点的最小关键字,再将根节点的所有子树按两趟合并法合并(具体见《数据结构与算法分析:java语言描述》Mark Allen Weiss著 第三版 12.6节)**合并:**具体见《数据结构与算法分析:java语言描述》Mark Allen Weiss著 第三版 12.6节C实现#includeiostream#includelist#includeutility#includevector#includerandomusingnamespacestd;templatetypenameTstructPairHeapNode{T data;PairHeapNode*prenullptr;PairHeapNode*right_siblingnullptr;PairHeapNode*first_childnullptr;PairHeapNode(constTd):data(d){}};templatetypenameTclassPairHeap{public:voidinsert(constTvalue);voiddecreaseKey(PairHeapNodeT*goal);boolremoveMinValue(Tmin_value);booldecreaseValue(constToriginal,constTchange_value);private:PairHeapNodeT*rootnullptr;staticPairHeapNodeT*unionSubHeap(PairHeapNodeT*left,PairHeapNodeT*right);staticPairHeapNodeT*unionAllChildSubHeap(PairHeapNodeT*start);pairPairHeapNodeT*,PairHeapNodeT*searchValueChanged(PairHeapNodeT*cur,constToriginal,PairHeapNodeT*parent);//pair的first为搜索节点父节点second为搜索节点};templatetypenameTpairPairHeapNodeT*,PairHeapNodeT*PairHeapT::searchValueChanged(PairHeapNodeT*cur,constToriginal,PairHeapNodeT*parent){if(cur-dataoriginal)return{nullptr,nullptr};if(cur-dataoriginal)return{parent,cur};PairHeapNodeT*runcur-first_child;while(run!nullptr){pairPairHeapNodeT*,PairHeapNodeT*resultsearchValueChanged(run,original,cur);if(result.second!nullptr){returnresult;}runrun-right_sibling;}return{nullptr,nullptr};}templatetypenameTboolPairHeapT::decreaseValue(constToriginal,constTchange_value){if(rootnullptr)returnfalse;if(originalchange_value)returnfalse;if(originalchange_value)returntrue;pairPairHeapNodeT*,PairHeapNodeT*resultsearchValueChanged(root,original,static_castPairHeapNodeT*(nullptr));if(result.secondnullptr)returnfalse;result.second-datachange_value;if(result.firstnullptr||result.first-datachange_value)returntrue;decreaseKey(result.second);returntrue;}templatetypenameTvoidPairHeapT::decreaseKey(PairHeapNodeT*goal){if(goal-pre-first_childgoal){goal-pre-first_childgoal-right_sibling;}else{goal-pre-right_siblinggoal-right_sibling;}if(goal-right_sibling!nullptr){goal-right_sibling-pregoal-pre;}PairHeapNodeT*resultunionSubHeap(goal,root);if(resultgoal){goal-right_siblingnullptr;goal-prenullptr;}}templatetypenameTboolPairHeapT::removeMinValue(Tmin_value){if(rootnullptr){returnfalse;}min_valueroot-data;PairHeapNodeT*tempnullptr;if(root-first_child!nullptr){tempunionAllChildSubHeap(root-first_child);}deleteroot;roottemp;returntrue;}templatetypenameTPairHeapNodeT*PairHeapT::unionAllChildSubHeap(PairHeapNodeT*start){listPairHeapNodeT*union_list;while(start!nullptrstart-right_sibling!nullptr){PairHeapNodeT*next_nextstart-right_sibling-right_sibling;PairHeapNodeT*tunionSubHeap(start,start-right_sibling);t-pret-right_siblingnullptr;union_list.push_back(t);startnext_next;}if(start!nullptr){start-prenullptr;union_list.push_back(start);}PairHeapNodeT*union_resultunion_list.back();typenamelistPairHeapNodeT*::const_reverse_iterator rununion_list.crbegin();run;while(run!union_list.crend()){union_resultunionSubHeap(*run,union_result);run;}returnunion_result;}templatetypenameTvoidPairHeapT::insert(constTvalue){PairHeapNodeT*new_nodenewPairHeapNodeT(value);rootunionSubHeap(new_node,root);}templatetypenameTPairHeapNodeT*PairHeapT::unionSubHeap(PairHeapNodeT*left,PairHeapNodeT*right){if(leftnullptr)returnright;if(rightnullptr)returnleft;if(left-dataright-data){right-right_siblingleft-first_child;if(right-right_sibling!nullptr){right-right_sibling-preright;}left-first_childright;right-preleft;returnleft;}else{left-right_siblingright-first_child;if(left-right_sibling!nullptr){left-right_sibling-preleft;}right-first_childleft;left-preright;returnright;}}intmain(){constintN2000;vectorinttest_data(N);for(size_t i0;itest_data.size();i){test_data[i]i1;}shuffle(test_data.begin(),test_data.end(),default_random_engine());PairHeapintobj;for(size_t i0;itest_data.size();i){cout插入test_data[i]endl;obj.insert(test_data[i]);}intmin;while(obj.removeMinValue(min)){cout当前最小值minendl;}coutendl;for(size_t i0;itest_data.size();i){test_data[i]iN;}shuffle(test_data.begin(),test_data.end(),default_random_engine());PairHeapintobj2;for(size_t i0;itest_data.size();i){cout插入test_data[i]endl;obj2.insert(test_data[i]);}for(size_t i0;itest_data.size();i){if(obj2.decreaseValue(iN,i)){cout将值iN减小至i成功!endl;}else{cout将值iN减小至i失败!endl;}}coutendl;return0;}