标题：采用堆的多路归并
出处：Felix021
时间：Tue, 23 Jun 2009 00:38:24 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1666

内容：
一般数据结构上用败者树来实现，这东西我没写过，所以暂时忽略之。
改用相对比较熟悉的heap来处理，写了一个class heap。
为了方便采用一个 5 x 5 的数组来存储需要归并的数据；很容易可以扩展到不定长的不同数据组。
明天再试着写一下败者树。

代码如下：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

struct node_t{
    int v, i;
    bool operator<(const node_t &a)const{
        return (v < a.v);
    }
    bool operator>(const node_t &a)const{
        return (v > a.v);
    }
    friend inline ostream & operator << (ostream &os, const node_t &t){
        os << t.v << " @ " << t.i;
        return os;
    }
};

template<typename T, class cmp = less<T> >
class heap{
    public:
        T d[500];
        int n;
        heap(){n = 1;}
        heap(int t, T a[]){
            init(t, a);
        }
        void init(int t, T a[]){
            d[0] = 0;
            for (int i = 0; i < t; ++i){
                d[i+1] = a[i];
            }
            n = t + 1;
            makeheap();
        }

        int size(){return (n - 1);}

        void makeheap(){
            for (int i = n / 2; i > 0; --i){
                siftdown(i);
            }
        }

        void siftdown(int i){
            if(i < 1 || i >= n) return;
            while(2 * i < n){
                i *= 2;
                if(i + 1 < n && cmp()(d[i], d[i+1])) i++; //选了大的
                if(cmp()(d[i/2], d[i])) swap(d[i/2], d[i]);
                else break;
            }
        }

        void siftup(int i){
            if(i < 1 || i >= n) return;
            while (i >= 1){
                if(cmp()(d[i/2], d[i])) swap(d[i/2], d[i]);
                else break;
                i /= 2;
            }
        }

        void dump(int i = 1, int dep = 0){
            if(i >= n) return;
            for (int j = 0; j < dep; ++j) printf("  ");
            cout << d[i] << endl;
            dump(2 * i, dep + 1);
            dump(2 * i + 1, dep + 1);
        }

        T remove(int i){
            T a = d[i];
            if(i < 1 || i >= n) throw(-4);
            d[i] = d[n-1];
            n--;
            if(cmp()(d[i], a)){
                siftdown(i);
            }else{
                siftup(i);
            }
            return a;
        }

        T removetop(){
            return remove(1);
        }

        void insert(T a){
            d[n++] = a;
            siftup(n - 1);
        }
};

int main(){
    int a[][5] = {
        {7,8,10,13,14},
        {0,3,6,12,19},
        {2,4,5,7,10},
        {15,17,19,21,23},
        {5,8,9,20,22}
    };
    int b[25], bi = 0;
    int idx[5];
    heap<node_t, greater<node_t> > h;

    for (int i = 0; i < 5; ++i){
        h[i].v = a[i][0];
        h[i].i = i;
        idx[i] = 1;
    }
    h.n = 6;
    h.makeheap();

    node_t tmp;
    while(h.n > 1){
        tmp = h.removetop();
        printf("~<FROM a[%d][%d]> %d\n", tmp.i, idx[tmp.i]-1, tmp.v);
        b[bi++] = tmp.v;
        if(idx[tmp.i] < 5){
            tmp.v = a[tmp.i][idx[tmp.i]++];
            h.insert(tmp);
        }
    }

    for (int i = 0 ; i< 25; ++i){
        printf("%d ", b[i]);
        if(i % 5 == 4) puts("");
    }

    return 0;
}



Generated by Bo-blog 2.1.0