c++ - 二项式堆 - 实现运行速度太慢

Question

我正在实现二项式堆。我已经或多或少地工作了，但我不明白为什么它这么慢。这是因为我实现 mergeHeaps 的方式吗？作为一系列“if”和“else if”语句来处理不同的条件？另一个问题是 deleteTree 不起作用。任何建议将不胜感激...

#include "pqueue-binomial-heap.h"
#include <cmath>
#include <bitset>
using namespace std;

BinomialHeapPQueue::BinomialHeapPQueue() {
    carry = NULL;
}

BinomialHeapPQueue::~BinomialHeapPQueue() {
}

string BinomialHeapPQueue::peek() const {
    int key = findKey();
    node *keynode = heap.get(key);
    string nextword = keynode->word;
    return nextword;
}

string BinomialHeapPQueue::extractMin() {
    int key = findKey();
    node *keynode = heap.get(key);
    string nextword = keynode->word;
    deleteNode(key);
    mergeHeaps();
    return nextword;
}

void BinomialHeapPQueue::enqueue(const string& elem) {
    node *newnode = new node;
    newnode->word = elem;
    if (heap.size() == 0) {
        heap.push_back(NULL);
    }
    newheap.push_back(newnode);
    mergeHeaps();
    logSize++;
}

int BinomialHeapPQueue::findKey() const {
    int minimum = 0;
    string minstring = "zzzzzzzzz";
    for (int i = 0; i < heap.size(); i++) {
        node *check = heap.get(i);
        if (check != NULL) {
        string checkstring = check->word;
        if (checkstring < minstring) {
            minimum = i;
            }
        }
    }
    return minimum;
}

void BinomialHeapPQueue::deleteNode(int key) {
    node *dnode = heap.get(key);
    newheap = dnode->children;
    dnode = NULL;
    logSize--;
    mergeHeaps();
}

void BinomialHeapPQueue::mergeHeaps() {
    int i = 0;

    while (i < heap.size() && i < newheap.size()) {
        node *currentp = heap.get(i);// node from heap
        node *currentq = newheap.get(i);// node from the newheap being merged into heap

        if (currentp == NULL && currentq == NULL && carry == NULL) {
            heap.set(i, NULL);
            i++;
        }
        else if (currentp != NULL && currentq != NULL && carry != NULL) {
            heap.set(i, currentp);
            carry = mergeTree(carry, currentq);
                if (i >= heap.size() - 1) {// extend vector/s if reaching the end and there's still something being carried.
                    heap.add(NULL);
            }
                if (i >= newheap.size() -1) {// better to do it this way than make one vector same size as the other- then enqueue gets expensive
                    newheap.add(NULL);
            }
            i++;
        }
        else if (currentp == NULL && currentq == NULL && carry != NULL) {
            heap.set(i, carry);
            carry = NULL;
            //deleteTree(carry); comment out deleteTree because it's not working right now.
            //carry = NULL;
            i++;
        }
        else if (currentp != NULL && currentq != NULL && carry == NULL) {
            carry = mergeTree(currentp, currentq);
            heap.set(i, NULL);
                if (i >= heap.size() - 1) {
                    heap.add(NULL);
            }
                if (i >= newheap.size() -1) {
                    newheap.add(NULL);
            }
            i++;
        }
        else if (currentp == NULL && currentq != NULL && carry != NULL) {
            carry = mergeTree(currentq, carry);
            heap.set(i, NULL);
                if (i >= heap.size() - 1) {
                    heap.add(NULL);
            }
                if (i >= newheap.size() -1) {
                    newheap.add(NULL);
            }
            i++;
        }
        else if (currentp != NULL && currentq == NULL && carry != NULL) {
            carry = mergeTree(currentp, carry);
            heap.set(i, NULL);
                if (i >= heap.size() - 1) {
                    heap.add(NULL);
            }
                if (i >= newheap.size() -1) {
                    newheap.add(NULL);
            }
            i++;
        }
        else if (currentp != NULL && currentq == NULL && carry == NULL) {
            i++;
        }
        else if (currentp == NULL && currentq != NULL && carry == NULL) {
            heap.set(i, currentq);
            i++;
        }
    }
    newheap.clear();

}

void BinomialHeapPQueue::deleteTree(node *tree) {
    if (tree == NULL) return;


    int size = tree->children.size();
    if (size > 0) {
    for (int i = 0; i < size; i++) {
        node *nexttree = tree->children.get(i);
        delete tree;
        deleteTree(nexttree);
        }
    }
    return;
}

void BinomialHeapPQueue::deleteVector(Vector<node *> &vec) {
    int vecsize = vec.size();
    for (int i = 0; i < vecsize; i++) {
        if (vec.get(i) != NULL) {
            node *startnode = vec.get(i);
            deleteTree(startnode);
        }
    }
    vec.clear();
}


BinomialHeapPQueue *BinomialHeapPQueue::merge(BinomialHeapPQueue *one, BinomialHeapPQueue *two) {

    return new BinomialHeapPQueue();
}


BinomialHeapPQueue::node *BinomialHeapPQueue::mergeTree(node *currentp, node *currentq) {
    string root1 = currentp->word;
    string root2 = currentq->word;
        if (root1 <= root2) {
            return addSubTree(currentp, currentq);
    }
        else {
            return addSubTree(currentq, currentp);
    }
}

BinomialHeapPQueue::node *BinomialHeapPQueue::addSubTree(node *root, node *add) {
    root->children.add(add);
    return root;
}

Answer 1

我认为这是您代码中较慢的部分:

while (i < heap.size() && i < newheap.size()) {
    node *currentp = heap.get(i);// node from heap
    node *currentq = newheap.get(i);//

get() 来自列表的不是常量，它在时间复杂度上是线性的。

使用此代码，合并操作的时间复杂度从 O(log n) 变为 O(log² n)。