堆排序 CPU 次

Question

我已经在 C++ 中实现了 Heapsort，它确实对数组进行了排序，但比预期的要高 CPU 次。它应该花费 nlog(n) 次触发器，并且它应该比至少比冒泡排序和插入排序更快地对其进行排序。

相反，它比冒泡排序和插入排序给了我更高的 cpu 倍。例如，对于一个随机的整数数组（大小为 100000），我有以下 cpu 次（以纳秒为单位）：

冒泡排序：1.0957e+11
插入排序：4.46416e+10
合并排序：7.2381e+08
堆排序：2.04685e+11

这是代码本身：

   #include <iostream>
    #include <assert.h>
    #include <fstream>
    #include <vector>
    #include <random>
    #include <chrono>
    using namespace std;

    typedef vector<int> intv;
    typedef vector<float> flov;
    typedef vector<double> douv;


        void max_heapify(intv& , int);
        void build_max_heap(intv& v);

        double hesorti(intv& v)
        {
            auto t0 =chrono::high_resolution_clock::now();
            build_max_heap(v);
            int x = 0;
            int i = v.size() - 1;
            while( i > x)
            {
                swap(v[i],v[x]);
                ++x;
                --i;
            }
            auto t1 = chrono::high_resolution_clock::now();
            double T = chrono::duration_cast<chrono::nanoseconds>(t1-t0).count();
            return T;
        }
        void max_heapify(intv& v, int i)
        {
            int left = i + 1, right = i + 2;
            int largest;
            if( left <= v.size() && v[left] > v[i])
            {
                largest = left;
            }

            else
            {
                largest = i;
            }

            if( right <= v.size() && v[right] > v[largest])
            {
                largest = right;
            }

            if( largest != i)
            {
                swap(v[i], v[largest]);
                max_heapify(v,largest);
            }



        }

        void build_max_heap(intv& v)
        {
            for( int i = v.size() - 2; i >= 0; --i)
            {
                max_heapify(v, i);
            }

        }

Answer 1

肯定是堆排序的实现有问题。

再看hesorti，可以看到调用build_max_heap后只是将vector的元素进行反转。所以不知何故 build_max_heap 不仅仅是堆，它实际上是对整个数组进行反向排序。

max_heapify 已经有一个问题：在堆的标准数组布局中，数组索引 i 处节点的子节点不是 i+1 和 i+2，但是 2i+1 和 2i+2.它是从 build_max_heap 数组的后面调用的。这是做什么的？

第一次调用它时，在最后两个元素上（当 i=n-2 时），它只是确保较大的先于较小的。之后调用它会发生什么？

让我们做一些数学归纳。假设，对于所有 j>i，在一个数组上用索引 j 调用 max_heapify 之后，其中数字 v [j+1] 到 v[n-1] 已经按降序排列，结果是数字 v[j] 到 v[n-1] 以降序排列。（我们已经看到当 i=n-2 时这是真的。）

如果 v[i] 大于或等于 v[i+1]（因此 v [i+2]），不会发生交换，当 max_heapify returns 时，我们知道 i 到 n-1以降序排列。另一种情况会怎样？

这里，largest设置为i+1，根据我们的假设，v[i+1]大于或等于 v[i+2]（实际上 v[k] 对于 k>i +1) 已经存在，因此针对 'right' 索引 (i+2) 的测试永远不会成功。 v[i] 与 v[i+1] 交换，使得 v[i]从 v[i] 到 v[n-1] 的最大数字，然后对来自的元素调用 max_heapify i+1到最后。根据我们的归纳假设，这将按降序对这些元素进行排序，因此我们知道现在所有从 v[i] 到 v[n-1] 的元素 降序排列。

然后通过归纳的力量，我们已经证明build_max_heap将对元素进行反向排序。它的方法是依次渗透元素，从后面开始，到它们在它后面的反向排序元素中的正确位置。

这看起来很眼熟吗？是插入排序！除了它是反向排序，所以当 hesorti 被调用时，交换序列将它置于正确的顺序。

插入排序也有 O(n^2) 平均行为，这就是为什么你得到与冒泡排序相似的数字。由于插入步骤的复杂实现，它几乎肯定会变慢。

TL;DR：您的堆排序并不快，因为它实际上不是堆排序，它是向后插入排序，然后是就地排序反转。

堆排序 CPU 次

Heapsort CPU time

c++

heapsort