[我的最大二进制堆中的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，因为这是您传递的参数的值。因此，将打印“无子元素”。
[我对代码甚至可以工作感到惊讶，因为leftChild和rightChild都返回-1，并且heapifyDown不检查返回值。结果，用于计算最大子级的代码将报告heap.size() > left，并将heap[-1]与heap[0]进行比较，并可能破坏程序的内存堆。这取决于数组开始之前内存中的内容。
我的建议是将您的leftChild函数修改为：
return (parentInd * 2) + 1;

并且对rightChild进行类似的修改。
在您的heapifyDown函数中，如果左孩子超出了堆的边界，则返回：
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);
    }
}