置换选择示例(1) 置换选择示例(2 3( 北大 置换选择示例(3) 置换选择算法的实现 存储 //模板参数Eem代表数组中每一个元素的类型 /A是从外存读入n个元素后所存放的数组 //in和out分别是输入和输出文件名 template <class Elem> void replacementselection(Elem A, int n, const char *in, const char outt 北大鳥”,翰究Pa957 张幅写 Elem mval//存放最小值堆的最小值 for(int last =(n-1); last > 0F mva= H heapArray[o];//最小值 Eemr;//存放从输入缓冲区中读入的元素 sendTooutputBuffer( input, output, * inputFile;//输入、输出文件句柄 inputFile, outputFile, mval; outputFile; put read(r);//从输入缓冲区读入一个记录 Buffer<Elem> input;//输入、输出 buffer if(less(r, mval) Buffer <Elem> output H heapArray[o]=r;//r放到根结点 //初始化输入输出文件 ese{//ast记录代誉根结点,r放到ast位量 init Files(inputFile, outputFile in, out); H heapArray [o]= h heap Array last] nitMinHeapArry(inputFile, n, A);∥/建堆 aStI= MinHeap<Elem> H(A, n, n) initInputBuffer(input, inputFile); H. SiftDown(O); //调整根结点 endup(output, inputFile, outputFile);) 1010 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 55 置换选择示例（1） 12 19 31 25 21 5 6 40 输 入 存 储 输 出 16 19 31 25 21 5 6 40 16 29 12 16 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 56 置换选择示例（2） 2 9 1 9 31 2 5 2 1 56 40 输 入 存 储 输 出 1 9 2 1 31 2 5 2 9 56 40 1 4 1 9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 57 置换选择示例（3） 4 0 21 31 25 29 56 14 输 入 存 储 输 出 2 1 25 31 40 29 56 14 35 21 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 58 置换选择算法的实现 //模板参数Elem代表数组中每一个元素的类型 //A是从外存读入n个元素后所存放的数组 //in和out分别是输入和输出文件名 template <class Elem> void replacementSelection(Elem * A, int n, const char * in, const char * out) { 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 59 Elem mval; //存放最小值堆的最小值 Elem r; //存放从输入缓冲区中读入的元素 FILE * inputFile; //输入、输出文件句柄 FILE * outputFile; Buffer<Elem> input; //输入、输出buffer Buffer<Elem> output; //初始化输入输出文件 initFiles(inputFile, outputFile, in, out); initMinHeapArry(inputFile, n, A); //建堆 MinHeap<Elem> H(A, n, n); initInputBuffer(input, inputFile); 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 60 for(int last = (n-1); last >= 0;){ mval = H.heapArray[0]; //最小值 sendToOutputBuffer(input, output, inputFile, outputFile, mval); input.read(r); //从输入缓冲区读入一个记录 if(!less(r, mval)) H.heapArray[0] = r; // r放到根结点 else { //last记录代替根结点，r放到last位置 H.heapArray[0]= H.heapArray[last]; H.heapArray[last] = r; H.setSize(last--); } H.SiftDown(0); //调整根结点 } //for endUp(output, inputFile, outputFile); }