多路归并的外排序 - vfdff的博客

作者在 2008-06-10 09:57:28 发布以下内容

//多路归并的外排序

    //思路如下:
    //1.按各输入文件中下一个读到的元素的大小构造一个输入流最小堆.
    //2.从堆顶文件里读一个元素并写入输出文件.
    //3.同时按读的那个文件的下一个元素的值调整堆.
    //4.若第3步已到达文件结尾.则从堆中删除该输入流
    //5 如果堆中还有元素. 回到第2步

#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<iterator>
#include<functional>
using namespace std;

    //这个类主要用来管理一个输入流.
    //它知道流中还有没有元素.
    //可以查看下一个将读出来的元素的值.
    //可以读出一个元素.
    template <class T>
    class Yudu {
    private:
        istream & _istream;
        T _next;
        bool _have_next;
    public:
        Yudu( istream & x) : _istream(x) {
            if (_istream >> _next) _have_next = true;
            else _have_next = false;
        }
        inline bool have_next() { return _have_next; }
        //读出流中下一个元素
        T read_next() {
            if (! _have_next) {
                cout << "读取错误! 退出" << endl;
                exit(1);
            }
            T temp = _next;
            if (_istream >> _next)
                _have_next = true;
            else
                _have_next = false;
            return temp;
        }
        //看看下一个元素但不读出来
        inline const T& look_next() const { return _next; }
    };

    //比较两个Yudu对象下一个元素的大小
    //提供给paixu函数中的堆操作时使用
    class bijiao
    {
    public:
        template <typename T>
        bool operator() (const Yudu<T>* a, const Yudu<T>* b) {
            return a->look_next() > b->look_next() ;
        }
    };

    //文件排序函数
    template <typename T>
    void paixu(vector<Yudu<T>* >& v , ostream& out){
        //先删除数组中的"没有下一个元素"的Yudu对象.例如一个空的文件构造的Yudu对象.
        v.erase( remove_if(v.begin(),v.end(),
            not1(mem_fun(& Yudu<T>::have_next))), v.end() );

make_heap(v.begin(), v.end(), bijiao());

        while (! v.empty() ){
            pop_heap(v.begin(),v.end(), bijiao());
            out << v.back()->read_next() << " ";   // out 以文本方式打开. 如果是其它方式这里要改.
            if (! v.back()->have_next() )
                v.pop_back();
            else
                push_heap(v.begin(), v.end(), bijiao());
        }
    }

    int main() {
        ifstream in[3];
        in[0].open("1.txt");
        in[1].open("2.txt");
        in[2].open("3.txt");

        vector<Yudu<int>* > v;
        v.push_back(new Yudu<int>(in[0])); //实际使用时要释放new出的对象.或者用boost的智能指针.
        v.push_back(new Yudu<int>(in[1]));
        v.push_back(new Yudu<int>(in[2]));

ofstream o("out.txt");

paixu(v, o);

        cin.get();
        return 0;
    }

    /*
    测试(三个文件中是已经有序的数)
    1.txt: 1 5 9 12 21
    2.txt: 3 4 5 7 8
    3.txt: 2 3 5 10 11 14 19 25 27

    执行归并后
    out.txt:
    1 2 3 3 4 5 5 5 7 8 9 10 11 12 14 19 21 25 27
    */