Binomial Heap in cpp

BinomialHeap.cpp

#include <iostream>
#include <queue>

using namespace std;

template<typename T>
struct BinomialHeap {
    struct Node {
        T x;
        int order;
        Node *c, *s;

        Node() : order(0), c(nullptr), s(nullptr) {}

        Node(const T &x, Node *c = nullptr, Node *s = nullptr) : x(x), order(0), c(c), s(s) {}

        void debug(int depth = 0) {
            for (int i = 0; i < depth; i++) cerr << " ";
            cerr << "tree(" << order << ")" << x << endl;
            if (c) c->debug(depth + 1);
            if (s) s->debug(depth);
        }
    } *root;

    void destruct(Node *ptr) {
        if (!ptr) return;
        destruct(ptr->c);
        destruct(ptr->s);
        delete ptr;
    }

    BinomialHeap() : root(nullptr) {}

    ~BinomialHeap() {
        destruct(root);
    }

    Node *link(Node *a, Node *b) {
        assert(a->order == b->order);
        if (a->x <= b->x) {
            ++a->order;
            if (!a->c) {
                a->c = b;
            } else {
                Node *ptr = a->c;
                while (ptr->s) ptr = ptr->s;
                ptr->s = b;
            }
            return a;
        } else return link(b, a);
    }

    Node *insert(Node *c, Node *s) {
        if (!s) return c;
        if (c->order == s->order) {
            Node *sib = s->s;
            s->s = nullptr;
            return insert(link(c, s), sib);
        } else {
            c->s = s;
            return c;
        }
    }

    Node *merge(Node *a, Node *b) {
        if (!a) return b;
        if (!b) return a;
        if (a->order < b->order) {
            a->s = merge(a->s, b);
            return a;
        } else if (a->order > b->order) {
            b->s = merge(a, b->s);
            return b;
        } else {
            Node *s = merge(a->s, b->s);
            a->s = b->s = nullptr;
            Node *c = link(a, b);
            return insert(c, s);
        }
    }

    void enqueue(const T &x) {
        Node *ptr = new Node(x);
        root = merge(root, ptr);
    }

    void find_top(Node *&_min_prev, Node *&_min_c) {
        Node *prev = nullptr, *c = root;
        Node *min_prev = nullptr, *min_c = root;
        while (c) {
            if (c->x < min_c->x) {
                min_c = c;
                min_prev = prev;
            }
            prev = c;
            c = c->s;
        }
        _min_prev = min_prev;
        _min_c = min_c;
    }

    T dequeue() {
        Node *min_prev, *min_c;
        find_top(min_prev, min_c);
        T x = min_c->x;
        if (min_prev) {
            min_prev->s = min_c->s;
        } else {
            root = min_c->s;
        }
        root = merge(min_c->c, root);
        delete min_c;
        return x;
    }

    const T &top() {
        Node *min_prev = nullptr, *min_c = root;
        find_top(min_prev, min_c);
        return min_c->x;
    }
};

int main() {
    BinomialHeap<int> heap;
    priority_queue<int, vector<int>, greater<int> > pq;
    for (int T = 0; T < 100; T++) {
        cerr << "Round " << T << endl;
        for (int i = 0; i < 100000; i++) {
            int data = rand() % 1000;
            heap.enqueue(data);
            pq.push(data);
        }
        for (int i = 0; i < 100000; i++) {
            assert(pq.top() == heap.top());
            pq.pop();
            heap.dequeue();
        }
    }

    return 0;
}