src/datastructure/radixheap.hpp

• View this file on GitHub
• Last update: 2020-05-08 21:35:33+09:00
• Include: #include "src/datastructure/radixheap.hpp"

Code

// D.key must be unsigned integer
template <class D> struct RadixHeap {
    using C = typename make_unsigned<decltype(D().key)>::type;
    static int bsr1(C x) { return (x == 0) ? 0 : bsr(x) + 1; }
    size_t sz = 0, cnt = 0;
    C last = 0;
    VV<D> v = VV<D>(sizeof(C) * 8 + 1);
    RadixHeap() {}
    void push(D x) {
        assert(decltype(x.key)(last) <= x.key);
        sz++;
        v[bsr1(x.key ^ last)].push_back(x);
    }
    void pull() {
        if (cnt < v[0].size()) return;
        int i = 1;
        while (v[i].empty()) i++;
        last = min_element(v[i].begin(), v[i].end(), [&](D l, D r) {
                   return l.key < r.key;
               })->key;
        for (D x : v[i]) {
            v[bsr1(x.key ^ last)].push_back(x);
        }
        v[i].clear();
    }
    D top() {
        pull();
        return v[0][cnt];
    }
    void pop() {
        pull();
        sz--;
        cnt++;
    }
    size_t size() const { return sz; }
    bool empty() const { return sz == 0; }
};

#line 1 "src/datastructure/radixheap.hpp"
// D.key must be unsigned integer
template <class D> struct RadixHeap {
    using C = typename make_unsigned<decltype(D().key)>::type;
    static int bsr1(C x) { return (x == 0) ? 0 : bsr(x) + 1; }
    size_t sz = 0, cnt = 0;
    C last = 0;
    VV<D> v = VV<D>(sizeof(C) * 8 + 1);
    RadixHeap() {}
    void push(D x) {
        assert(decltype(x.key)(last) <= x.key);
        sz++;
        v[bsr1(x.key ^ last)].push_back(x);
    }
    void pull() {
        if (cnt < v[0].size()) return;
        int i = 1;
        while (v[i].empty()) i++;
        last = min_element(v[i].begin(), v[i].end(), [&](D l, D r) {
                   return l.key < r.key;
               })->key;
        for (D x : v[i]) {
            v[bsr1(x.key ^ last)].push_back(x);
        }
        v[i].clear();
    }
    D top() {
        pull();
        return v[0][cnt];
    }
    void pop() {
        pull();
        sz--;
        cnt++;
    }
    size_t size() const { return sz; }
    bool empty() const { return sz == 0; }
};

Back to top page