Leftist Heap
(Heap/LeftistHeap.hpp)

• View this file on GitHub
• Last update: 2023-04-05 23:10:22+09:00
• Include: #include "Heap/LeftistHeap.hpp"

概要

http://hos.ac/blog/#blog0001

heapの併合，meldが可能

Verified with

• test/AOJ_ALDS1_9_C.test.cpp

Code

template<typename T,bool less=true>
struct LeftistHeap{
    struct Node{
        Node *l,*r;
        int s;
        T val;
        Node(T val):l(nullptr),r(nullptr),s(1),val(val){}
    };
    Node *root;
    LeftistHeap(Node *t=nullptr):root(t){}

    Node *meld(Node *a,Node *b){
        if(!a or !b) return (a?a:b);
        if((a->val>b->val)^(!less)) swap(a,b);
        a->r=meld(a->r,b);
        if(!a->l or a->l->s<a->r->s) swap(a->l,a->r);
        a->s=(a->r?a->r->s:0)+1;
        return a;
    }
    void meld(LeftistHeap b){
        root=meld(root,b.root);
    }
    void push(T x){
        root=meld(root,new Node(x));
    }
    T pop(){
        assert(root!=nullptr);
        T ret=root->val;
        root=meld(root->l,root->r);
        return ret;
    }
    T top(){
        assert(root!=nullptr);
        return root->val;
    }
    bool empty(){
        return root==nullptr;
    }
};

#line 1 "Heap/LeftistHeap.hpp"
template<typename T,bool less=true>
struct LeftistHeap{
    struct Node{
        Node *l,*r;
        int s;
        T val;
        Node(T val):l(nullptr),r(nullptr),s(1),val(val){}
    };
    Node *root;
    LeftistHeap(Node *t=nullptr):root(t){}

    Node *meld(Node *a,Node *b){
        if(!a or !b) return (a?a:b);
        if((a->val>b->val)^(!less)) swap(a,b);
        a->r=meld(a->r,b);
        if(!a->l or a->l->s<a->r->s) swap(a->l,a->r);
        a->s=(a->r?a->r->s:0)+1;
        return a;
    }
    void meld(LeftistHeap b){
        root=meld(root,b.root);
    }
    void push(T x){
        root=meld(root,new Node(x));
    }
    T pop(){
        assert(root!=nullptr);
        T ret=root->val;
        root=meld(root->l,root->r);
        return ret;
    }
    T top(){
        assert(root!=nullptr);
        return root->val;
    }
    bool empty(){
        return root==nullptr;
    }
};

Back to top page