Binomial Queue

没啥讲的，直接上代码

代码

class node{
public:
    int key;
    int id;
    int rank;
    node* left_child;
    node* next_sibling;    
    node(){key = 0, id = 0, rank = 0, left_child = NULL, next_sibling = NULL;}
    node(int key, int id) : key(key), id(id) {rank = 0, next_sibling = NULL, left_child = NULL;}
    friend class BinTree;
};    
bool LEQ(node* X, node* Y){
    return X->key == Y->key ? X->id < Y->id : X->key < Y->key;
}
class BinTree{
public:
    node* root;    
    friend class BinQueue;
    BinTree(){root = NULL;}
    void dfs(node* u){
        if(!u) return;
        cerr<<u->key<<" ";
        if(u->left_child) dfs(u->left_child);
        if(u->next_sibling) dfs(u->next_sibling);
    }
    void traverse(){
        dfs(root);
    }
};

class BinQueue{
public:
    static const int LOGN = 20;
    int size;
    int MinId;
    BinTree* Min;
    BinTree* Trees[LOGN];
    BinQueue(){
        size = 0, MinId = -1, Min = NULL;
        for(int i = 0; i < LOGN; ++i) Trees[i] = NULL;
    }
    void Traverse(){
        for(int i = 0; i < LOGN; ++i){
            if(Trees[i]) Trees[i]->traverse();
        }
    }
};
BinTree* CombineTrees(BinTree* X, BinTree* Y){
    if(LEQ(Y->root, X->root)) swap(X, Y);
    Y->root->next_sibling = X->root->left_child;
    X->root->left_child = Y->root;
    ++X->root->rank;
    return X;
}

BinQueue* Merge(BinQueue* X, BinQueue* Y){
    BinTree* S;
    BinTree* T;
    BinTree* Carry = NULL;
    BinTree* Min = NULL;
    int MinId = -1;
    X->size += Y->size;
    for(int i = 0; i < X->LOGN; ++i){
        S = X->Trees[i], T = Y->Trees[i];
        switch(4*!!Carry + 2*!!T + !!S){
            case 0:
            case 1: break;
            case 2:
                X->Trees[i] = T; Y->Trees[i] = NULL; break;
            case 3:
                Carry = CombineTrees(S, T);
                X->Trees[i] = Y->Trees[i] = NULL;
                break;
            case 4:
                X->Trees[i] = Carry; Carry = NULL; break;
            case 5:
                Carry = CombineTrees(S, Carry); X->Trees[i] = NULL; break;
            case 6:
            case 7:
                Carry = CombineTrees(T, Carry); Y->Trees[i] = NULL; break;
        }
        //change Min if necessary
        if(!Min || X->Trees[i] && LEQ(X->Trees[i]->root, Min->root)) 
            Min = X->Trees[i], MinId = i;
    }
    X->Min = Min, X->MinId = MinId;
    delete(Y);
    return X;
}
BinTree* MakeTree(node* root){
    BinTree* H = new BinTree();
    H->root = root;
    H->root->next_sibling = NULL;
    return H;
}
int FindMin(BinQueue* H){
    return H->Min->root->key;
}
void InsertKey(BinQueue* H, int key, int id){
    assert(H != NULL);
    BinQueue* X = new BinQueue();
    node* x = new node(key, id);
    X->Trees[0] = MakeTree(x);
    X->size = 1;
    H = Merge(H, X);
}
int DeleteMin(BinQueue* H){
    BinQueue* DeleteQueue = new BinQueue();
    assert(H != NULL);
    int ret = FindMin(H);
    node* x = H->Min->root->left_child;
    while(x != NULL){
        int i = x->rank;
        node* w = x;
        node* next = x->next_sibling;
        DeleteQueue->Trees[i] = MakeTree(w);
        DeleteQueue->size += (1 << DeleteQueue->Trees[i]->root->rank);
        x = next;
    }
    H->Trees[H->MinId] = NULL;
    H->size -= (1 << H->Min->root->rank);
    delete(H->Min);
    H->Min = NULL, H->MinId = -1;
    H = Merge(H, DeleteQueue);
    return ret;
}

模板类

template<typename T> class BinTree;
template<typename T> class BinQueue;
template<typename T> class BinNode{
public:
    T key;
    int rank; // rank of node, if rank is k, then size of subtree of this node is 2^k
    BinNode<T>* left_child;
    BinNode<T>* next_sibling;    
    BinNode<T>* parent;
    BinNode<T>(){key = 0, rank = 0, left_child = NULL, next_sibling = NULL;}
    BinNode<T>(T key) : key(key) {rank = 0, next_sibling = NULL, left_child = NULL;}
    friend class BinTree<T>;
};    
template<typename T> class BinTree{
public:
    BinNode<T>* root; 
    friend class BinQueue<T>;
    BinTree<T>(){root = NULL;}
};
template<typename T> class BinQueue{
public:
    static const int LOGN = 20;
    int size;
    int MinId;
    BinTree<T>* Min; // Min pointer
    BinTree<T>* Trees[LOGN]; // forest
    BinQueue<T>(){
        size = 0, MinId = -1, Min = NULL;
        for(int i = 0; i < LOGN; ++i) Trees[i] = NULL;
    }
    bool empty(){
        return size == 0;
    }
    void MakeBinQueue(){
        size = 0, MinId = -1, Min = NULL;
        for(int i = 0; i < LOGN; ++i) Trees[i] = NULL;
    }
};
template<typename T> BinQueue<T>* Merge(BinQueue<T>* X, BinQueue<T>* Y);
template<typename T> BinTree<T>* MakeTree(BinNode<T>* root);
template<typename T> void InsertKey(BinQueue<T>* H, T key);
template<typename T> BinNode<T>* DeleteMin(BinQueue<T>* H);
template<typename T> void DecreaseKey(BinQueue<T>* H, BinNode<T>* x, T k);
template<typename T> BinNode<T>* FindMin(BinQueue<T>* H);

template<typename T> bool LEQ(BinNode<T>* X, BinNode<T>* Y){
    return X->key < Y->key;
}

template<typename T> BinTree<T>* CombineTrees(BinTree<T>* X, BinTree<T>* Y){ // combine two trees
    if(LEQ(Y->root, X->root)) swap(X, Y);
    Y->root->next_sibling = X->root->left_child;
    X->root->left_child = Y->root;
    Y->root->parent = X->root;
    ++X->root->rank;
    delete(Y); // delete is necessary, otherwise space is not O(n)
    return X;
}

template<typename T> BinQueue<T>* Merge(BinQueue<T>* X, BinQueue<T>* Y){ // merge two queues
    BinTree<T>* S;
    BinTree<T>* M;
    BinTree<T>* Carry = NULL;
    BinTree<T>* Min = NULL;
    int MinId = -1;
    X->size += Y->size;

    for(int i = 0; i < X->LOGN; ++i){
        S = X->Trees[i], M = Y->Trees[i];
        switch(4*!!Carry + 2*!!M + !!S){
            case 0:
            case 1: break;
            case 2:
                X->Trees[i] = M; Y->Trees[i] = NULL; break;
            case 3:
                Carry = CombineTrees(S, M);
                X->Trees[i] = Y->Trees[i] = NULL;
                break;
            case 4:
                X->Trees[i] = Carry; Carry = NULL; break;
            case 5:
                Carry = CombineTrees(S, Carry); X->Trees[i] = Y->Trees[i] = NULL; break;
            case 6:
            case 7:
                Carry = CombineTrees(M, Carry); Y->Trees[i] = NULL; break;
        }
        //change Min if necessary

        if(!Min || X->Trees[i] && LEQ(X->Trees[i]->root, Min->root)) Min = X->Trees[i], MinId = i;
    }
    X->Min = Min, X->MinId = MinId;
    delete(Y);
    return X;
}
template<typename T> BinTree<T>* MakeTree(BinNode<T>* root){ // make a new tree containing a node
    BinTree<T>* H = new BinTree<T>();
    H->root = root;
    H->root->next_sibling = H->root->parent = NULL;
    return H;
}
template<typename T> BinNode<T>* FindMin(BinQueue<T>* H){
    return H->Min->root;
}
template<typename T> void InsertKey(BinQueue<T>* H, T key){
    assert(H != NULL);
    BinQueue<T>* X = new BinQueue<T>(); 
    BinNode<T>* x = new BinNode<T>(key); 
    X->Trees[0] = MakeTree(x); 
    X->size = 1; 
    H = Merge(H, X); 
}
template<typename T> BinNode<T>* DeleteMin(BinQueue<T>* H){
    BinQueue<T>* DeleteQueue = new BinQueue<T>();
    assert(H != NULL);
    BinNode<T>* ret = FindMin(H);
    BinNode<T>* x = H->Min->root->left_child;
    while(x != NULL){ // create a new queue containing subtrees of Min tree
        int i = x->rank;
        BinNode<T>* w = x;
        BinNode<T>* next = x->next_sibling;
        DeleteQueue->Trees[i] = MakeTree(w);
        DeleteQueue->size += (1 << DeleteQueue->Trees[i]->root->rank);
        x = next;
    }
    H->Trees[H->MinId] = NULL;
    H->size -= (1 << H->Min->root->rank); // delete Min tree from original queue
    delete(H->Min);
    H->Min = NULL, H->MinId = -1;
    H = Merge(H, DeleteQueue);
    return ret;
}
template<typename T> void DecreaseKey(BinQueue<T>* H, BinNode<T>* x, T k){
    assert(k <= x->key);
    x->key = k;
    while(x->parent != NULL && LEQ(x, x->parent)){ // campare x with parent y
        swap(x->key, x->parent->key);
        x = x->parent;
    }
    if(x->parent == NULL /*root*/ && LEQ(x, H->Min->root)) H->Min->root = x;
}

与 Fibonacci Heap 复杂度对比

还是 Fibonacci Heap 更快一些