二项堆

二叉堆

template<typename T,size_t _n>
struct hep{
    int n;T *q;
    hep(){n=0;q=new int[_n];}
    ~hep(){delete []q;}
    void up(int i){ //上浮
        for(;i>1;i>>=1)
        if(q[i]<q[i>>1])swap(q[i],q[i>>1]);
    }
    void down(int i){ //下浮
        while((i<<1)<=n){
            int k=i<<1;
            if(k<n&&q[k+1]<q[k])++k;
            if(q[i]>q[k])swap(q[i],q[k]),i=k;
            else return;
        }
    }
    void push(const T& x){
        q[++n]=x;up(n);
    }
    void pop(){
        swap(q[1],q[n--]);
        down(1);
    }
    T top(){return q[1];}
    bool empty(){return n==0;}
};

二项堆

定义：

• 度数为0的二项树只包含一个结点
• 度数为的二项树有一个根结点，根结点下有个子女，每个子女分别是度数分别为的二项树的根
  
• 度数为的二项树共有个节点，深度为处有个节点。
• 每棵二项树都满足最小堆性质，即结点关键字大于等于其父结点的值
• 不能有两棵或以上的二项树有相同度数（包括度数为0）。换句话说，具有度数k的二项树有0个或1个。
  比如的二进制为,所以由度数为的三棵树组成。
  
• 二项堆插入操作，平摊分析复杂度为,个节点的堆，最多有棵树，查找，删除时间为。
  二项堆的内存结构图：
  

template<typename T>
struct BinomiaNode{
    BinomiaNode():degree(0){
        val=0;
        parent=NULL;child=NULL;next=NULL;
    }
    T val;
    BinomiaNode *parent;
    BinomiaNode *child;
    BinomiaNode *next;
    size_t degree;
};

template<typename T,typename node=BinomiaNode<T>>
class BinomiaHeap{
public:
    BinomiaNode(){root=NULL;}
    bool empty()const{return root==NULL;}
    T top(){
        assert(empty());
        node *p=root;T key=root->val;
        while(p){
            if(p->val<key)key=p->val;
            p=p->next;
        }
        return key;
    }
    void pop(){
        erase(top());
    }
    void union_heap(BinomiaHeap<T> rhs){
        if(rhs&&rhs.root)root=union_heap(root,rhs.root);
    }
    void insert(const T& key){
        if(find(key))return;
        node* rt=new node();
        rt->val=key;
        root=union_heap(root,rt);
    }
    bool find(const T& key){return search(root,key)!=NULL;}
    void erase(const T& key){
        root=erase(root,key);
    }
private:
    node* erase(node* rt,const T& key){
        if(rt==NULL)return rt;
        node *p=search(rt,key);
        if(p==NULL)return rt;
        node* parent=p->parent;
        while(parent){
            p->val^=parent->val^=p->val;
            p=parent;parent=parent->parent;
        }
        node *prev=NULL;
        node *pos=rt;
        while(pos!=p)prev=pos,pos=pos->next;
        if(prev)prev->next=p->next;
        else rt=p->next;
        rt=union_heap(rt,reverse(p->child));
        p=NULL;return rt;
    }
    node* search(node* rt,const T& key){
        node *child,*parent=rt;
        while(parent){
            if(parent->val==key)return parent;
            else {
                child=search(parent->child,key);
                if(child)return child;
                parent=parent->next;
            }
        }
        return NULL;
    }
    node* reverse(node* rt){
        if(rt==NULL)return rt;
        node *_next,*tail=NULL;
        rt->parent=NULL;
        while(rt->next){
            _next=rt->next;
            rt->next=tail;
            tail=rt;rt=_next;
            rt->parent=NULL;
        }rt->next=tail;
        return rt;
    }

    void link(node* &child,node* &rt){
        child->parent=rt;
        child->next=rt->child;
        rt->child=child;rt->degree++;
    }
    node* merge(node* h1,node* h2){
        if(!h1)return h2;
        if(!h2)return h1;
        node* rt=NULL,*_next=NULL,*h=NULL;
        while(h1&&h2){
            if(h1->degree<=h2->degree)
            h=h1,h1=h1->next;
            else h=h2,h2=h2->next;

            if(_next==NULL){
                _next=h;rt=h;
            }else{
                _next->next=h;
                _next=h;
            }
            if(!h1&&h2)_next->next=h2;
            if(h1&&!h2)_next->next=h1;
        }
        return rt;
    }
    node* reverse_list(node* rt){
        if(rt==NULL)return rt;
        node* p=NULL;
        while(rt){
            node* q=rt;
            rt=rt->next;
            q->next=p;
            p=q;
        }
        return p;
    }
    node* union_heap(node* h1,node* h2){
        node* rt=merge(h1,h2);
        if(rt==NULL||rt->next==NULL)return rt;
        rt=reverse_list(rt);
        stack<node*>S;
        for(node *p=rt;p;p=p->next){
            while(!S.empty()&&S.top()->degree==p->degree){
                node* q=S.top();
                link(q,p);
                S.pop();
            }
            S.push(p);
        }
        node* p=NULL;
        while(!S.empty()){
            node* q=S.top();
            S.pop();
            q->next=p;
            p=q;
        }
        return reverse_list(p);
    }
    node *root;
};

合并操作：

删除操作：