我的最大二进制堆中的 C++ 轮询操作工作得非常慢

Question

我正在用 C++ 实现最大二进制堆，它似乎工作正常。

但是，当我重复轮询操作(我的代码中的 delMax 方法)直到堆为空时，它花费的时间太长，它比构建堆本身要长，以防 10^ 7 个元素大约需要 6 秒，而我被告知几乎不需要时间。

此外，在打印堆摘要和打印删除时间之间，我打印了两次“Childless element!”(来自 leftChild 和 rightChild方法)，但我不知道这是从哪里来的，因为那里没有调用这些方法。

我的代码:

  #include "pch.h"
  #include <iostream>
  #include "time.h"
  #include <random>
  #include <string>
  #include <functional>
  #include <vector>
 using namespace std;
 template <typename T>
 class BinaryHeap;

template <typename T>
class BinaryHeap
{
vector <T> heap;
int getParent(int childInd)
{
    if (heap.size() == 0)
    {
        return -1;
    }
    //int parent = 0;
    int parent = floor((childInd - 1) / 2);
    if (heap.size() <= childInd)
    {
        cout << "No such element!" << endl;
        return -1;
    }
    else
        return parent;
}
int leftChild(int parentInd)
{
    int left = floor(2 * parentInd + 1);
    if (heap.size() <= parentInd)
    {
        cout << "Childless element!" << endl;
        return -1;
    }
    else
        return left;
}
int rightChild(int parentInd)
{
    int right = (2 * parentInd + 2);
    if (heap.size() <= parentInd)
    {
        cout << "Childless element!" << endl;
        return -1;
    }
    else
        return right;
}
void heapifydown(int index)
{
    int left = leftChild(index);
    int right = rightChild(index);
    int largest = index;
    if (heap.size() > left&&heap[left] > heap[index])
    {
        largest = left;
    }
    if (heap.size() > right&& heap[right] > heap[largest])
    {
        largest = right;
    }
    if (largest != index)
    {
        int temp = heap[index];
        heap[index] = heap[largest];
        heap[largest] = temp;
        heapifydown(largest);
    }
}
void heapifyup(int index)
{
    int p = getParent(index);
    if (heap.size() > index&& heap[p] < heap[index])
    {
        int temp = heap[index];
        heap[index] = heap[p];
        heap[p] = temp;
        heapifyup(p);
    }
}

public:
BinaryHeap() {};
~BinaryHeap()
{
    heap.clear();
}
void addElement(T el)
{
    heap.push_back(el);
    int index = heap.size() - 1;
    heapifyup(index);
}
void printHeap()
{
    if (heap.size() == 0)
    {
        cout << "Empty heap!" << endl;
        return;
    }
    for (int i = 0; i < heap.size(); i++)
    {

        cout << heap[i] << endl;
    }
}
T delMax()
{
    if (heap.size() == 0)
    {
        return -1;
    }
    T temp = heap[0];
    T temp2 = heap[0];
    heap[0] = heap.at(heap.size()-1);
    heap.pop_back();
    //T parent = 0;
    //T child = 2 * parent + 2;
    heapifydown(0);
    return temp;
    //delete &temp;
}
void clearHeap()
{
    for (int i = heap.size(); i > 0; --i)
    {
        heap.pop_back();
    }
}
void print()
{
    if (heap.size() == 0)
    {
        cout << "Empty heap!" << endl;
        return;
    }
    cout << "Size: " << heap.size()<<endl;
    cout << " Root: " << heap[0] << endl;
    cout << "L. child: " << heap[1] << endl;
    cout << "R. Child: " << heap[2] << endl;
    cout << "3 last elements: " << heap[heap.size()-3] <<
    " "<<heap[heap.size() - 2]<<
    " "<<heap[heap.size() - 1]<<endl;
}
};
int randomInt()
{
static default_random_engine generator{ 10 };
static uniform_int_distribution<int> rozklad{ 0, 11000000 };
static function<int()> los{ bind(rozklad, generator) };
int l = los();
return l;
}
int main()
{
BinaryHeap<int>*bh = new BinaryHeap<int>();
const int MAX_ORDER = 7; // maksymalny rzad wielkosci dodawanych danych
for (int i = 1; i <= MAX_ORDER; i++)
{
    const int n = pow(10, i);
    clock_t start1 = clock();
    for (int i = 0; i < n; i++)
    {
        int el = randomInt();
        bh->addElement(el);
    }
    clock_t stop1 = clock();
    double adding_time = (stop1 - start1) / (double)CLOCKS_PER_SEC;
    cout << "Adding time: " << adding_time << "s" << endl;
    bh->print();
    clock_t start2 = clock();
    for (int j = 0; j < n; j++)
    {
        int out = bh->delMax();
        //cout << "WyciagniEty: "<<bh->delMax()<<endl;
        //delete &out;
    }
    clock_t stop2 = clock();
    double polling_time = (stop2 - start2) / (double)CLOCKS_PER_SEC;
    cout << "Removing time: " << polling_time << "s" << endl;
    bh->print();
    bh->clearHeap();
}
delete bh;
return 0;
}

Answer 1

当父索引小于或等于堆大小时，“无子元素”消息可能会出现在 leftChild 和 rightChild 函数中。通过检查您的代码，我会说当您尝试删除堆中的最后一个节点时会发生这种情况。考虑您的 delMax 函数(我已经删除了死代码和注释掉的代码):

T delMax()
{
    if (heap.size() == 0)
    {
        return -1;
    }
    T temp = heap[0];
    heap[0] = heap.at(heap.size()-1);
    heap.pop_back();
    heapifydown(0);
    return temp;
}

当堆大小为 1 时，调用 heap.pop_back() 删除最后一个元素，现在大小为 0。然后调用 heapifydown(0).

heapifydown 调用leftChild 和rightChild，它们都包含这段代码:

if (heap.size() <= parentInd)
{
    cout << "Childless element!" << endl;
    return -1;
}
else

heap.size() 返回 0，因为堆是空的。 parentInd 为 0，因为这是您传递的参数的值。因此，打印了“Childless element”。

令我感到惊讶的是代码竟然可以工作，因为 leftChild 和 rightChild 都返回 -1，而 heapifyDown 没有t 检查返回值。结果，计算最大子节点的代码将报告 heap.size() > left，并将 heap[-1] 与 heap 进行比较[0]，并且可能会破坏程序的内存堆。这取决于数组开始之前内存中的内容。

我的建议是将您的 leftChild 函数修改为:

return (parentInd * 2) + 1;

并对rightChild做类似的修改。

在您的 heapifyDown 函数中，如果左 child 超出堆的边界则返回:

void heapifydown(int index) {
    int left;
    int right;
    int largest = index;

    left = leftChild(index);
    if (heap.size() <= left) {
        // left child index is outside range of the heap.
        // node has no children, so return.
        return;
    }

    if (heap[left] > heap[index]) {
        largest = left;
    }

    right = rightChild(index);
    if (heap.size() > right && heap[right] > heap[largest])
    {
        largest = right;
    }
    if (largest != index)
    {
        int temp = heap[index];
        heap[index] = heap[largest];
        heap[largest] = temp;
        heapifydown(largest);
    }
}