Левая куча сливается ОЧЕНЬ медленно

Question

Моя реализация работает правильно с небольшим количеством отслеживаемых элементов. Эта левая куча занимает несколько секунд для вставки 50 000 элементов, а для перекосной кучи - несколько миллисекунд.

Поэтому я считаю, что алгоритм реализован правильно, но не эффективно.

struct Lode
{
    int getRank()
    {
        rank = 1;

        if (left || right)
        {
            int rankL = 0, rankR = 0;

            if (left)  rankL =  left->getRank();
            if (right) rankR = right->getRank();

            if (rankL < rankR)
                rank = rankL + 1;
            else
                rank = rankR + 1;
        }
        return rank;
    }
};

struct Leap
{
    Lode* merge(Lode* x, Lode* y)
    {
        if (!x) return y;
        if (!y) return x;

        if (x->data > y->data)
            swap(x,y);

        x->right = merge(x->right, y);

        x->getRank();
        int rankL = 0, rankR = 0;
        if (x->left)  rankL = x->left->rank;
        if (x->right) rankR = x->right->rank;

        if (rankL < rankR)
            swap(x->left, x->right);

        return x;
    }
}

Неправильный код (?) Опущен.

Answer 1

Это была проблема с вычислением ранга, как сказал molbdnilo. Единственный необходимый расчет

x->rank = x->right->rank + 1;

Рекурсивно запрашивать у каждого дочернего узла его ранг совершенно не нужно и неэффективно.