運行得太慢的二項式堆實現

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（日誌 n）。