小编eve*_*ett的帖子

在我的堆和未排序的列表中插入100000000个元素之后,堆插入实际上似乎更快(12秒对20秒).为什么是这样？我相信堆插入是O(logn)在未排序的列表插入时O(1).我还注意到我的堆插入实现实际上并没有随着输入的数量而扩展.这也让我感到困惑.

这是我运行的代码:

int main ()
{
    clock_t unsortedStart;
    clock_t heapStart;

    double unsortedDuration;
    double heapDuration;

    int num_pushes = 100000000;
    int interval = 10000;

    ofstream unsorted ("unsorted.txt");
    ofstream heap ("heap.txt");

    UnsortedPQ<int> unsortedPQ; 
    HeapPQ<int> heapPQ; 

    unsortedStart = clock();

    for (int i = 0; i < num_pushes; ++i)
    {
        if (i % interval == 0) {
            unsortedDuration = ( clock() - unsortedStart ) / (double) CLOCKS_PER_SEC;
            unsorted << unsortedDuration << " " << i << endl;
        }

        unsortedPQ.insertItem(rand() % 100); …