第8章图 求解过程中并查集与堆的变化 ④⑥ 选(345)山区4区30国68]选566)①3山区4②B ④⑥ D② 23 选(127)[3山[249 选(357)⑥3山 ②④⑤ 21310 ④ 山 ⑥选(3.6.)在同一连通分量上,不加②⑥选(249,结束 最后得到的生成树如下 6 并查集的存储表示 完整的程序如下 #include <iostream. h? template <class Type> class MinHeap i num MaxHeapsize=503: MinHeap( int Maxsize MaxHeap Size ) MinHeap( type array[, int n ) void Insert( const Type &ele ) void RemoveMin( Type &Min ) void Output O private void Filter Down( int start, int end ) void FilterUp( int end )i Type "pl int Currentsize; class UFSets i第 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: 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 ③ ④ 1 3 11 5 6 6 1 2 7 3 5 7 选(3,4,5) 2 4 9 2 3 10 3 6 8 ③ ④ ⑤ ⑥ 选(5,6,6) 1 3 11 1 2 7 3 5 7 2 4 9 2 3 10 3 6 8 ③ ④ ⑤ ⑥ 选(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 并查集的存储表示