第8章图 选45国山国2图8]速6山区p]B 357 B3681 ②@Bd②E4 2310 选2n)血E 选(357)⑥[3山i ②④⑤ 2 ④ ⑥选(3.68),在同一连通分量上,不加②⑥选(24.9),结束 最后得到的生成树如下 6 并查集的存储表示 完整的程序如下 #include <iostream. h template <class Type> class MinHeap i enum i Maxheap Size=50; MinHeap( int Maxsize MaxHeap Size ) MinHeap( Type array[l int n ) void Insert( const Type &ele ) oid RemoveMin( Type &Min ) id Output (; private: void Filter Down( int start, int end ) void FilterUp( int end ) Type *pHe int Currentsize; class UFSets i enum i MaxUnionS UFSets( int MaxSize MaxUnionS ize ) UFSetsoi delete []m pArent; 3第 8 章 图 101 最后得到的生成树如下 完整的程序如下: #include <iostream.h> template <class Type> class MinHeap { public: enum { MaxHeapSize = 50 }; MinHeap ( int Maxsize = MaxHeapSize ); MinHeap ( Type Array[ ], int n ); void Insert ( const Type &ele ); void RemoveMin ( Type &Min ); void Output (); private: void FilterDown ( int start, int end ); void FilterUp ( int end ); Type *pHeap; int HMaxSize; int CurrentSize; }; class UFSets { public: enum { MaxUnionSize = 50 }; UFSets ( int MaxSize = MaxUnionSize ); ~UFSets () { delete [ ] m_pParent; } 3 1 -6 3 3 5 1 3 11 3 5 7 2 4 9 3 6 8 2 3 10 ① ② ③ ④ ⑤ ⑥ 6 7 7 5 9 ④ 选(3,4,5) 1 3 11 2 4 9 2 3 10 3 6 8 选(5,6,6) 1 3 11 2 4 9 2 3 10 ③ ④ ⑤ ⑥ 选(1,2,7) ① ② ③ ④ ⑤ 选(3,5,7) ⑥ ① ② 1 3 11 2 4 9 2 3 10 3 6 8 ③ ④ ⑤ ⑥ 选(3,6,8), 在同一连通分量上, 不加 ① ② 1 3 11 2 3 10 2 4 9 ③ ④ ⑤ ⑥ 选(2,4,9), 结束 ① ② 1 3 11 2 3 10 0 1 2 3 4 5 6 并查集的存储表示