仅使用递归构建最小堆

Question

这是尝试让堆排序仅通过函数调用来构建堆。问题是完成时间太长，比在同一项目中编写的更简单的冒泡排序要长，将近 100 秒，而冒泡的 42 有 100000 个条目，按降序排列。合并排序和快速排序从来没有超过一秒钟。如果编译器未能进行尾调用优化，请不要介意它在 100000 时崩溃。

它曾经崩溃，一些关于实现的细节是为了让尾调用发生。它已经在下降、上升和随机分布的数据上进行了测试。还进行了一些更改以弥补它的速度有多慢，是什么让它看起来很混乱。

int heap_sort_step(int v[], int len, int i){
    int nextl = 2 * i + 1, nextr = nextl + 1;
    char bfl = (nextl<len)|((nextr<len)<<1);

    switch(bfl)
    {
        case 3:
        case 2:
            while(v[i] > heap_sort_step(v, len, nextr))
                swap(v + i, v + nextr);
        case 1:
            while(v[i] > heap_sort_step(v, len, nextl))
                swap(v + i, v + nextl);
        default:
            return v[i];
    }

}

void heap_sort(int v[], int len){
    return (len > 1)?
                (heap_sort_step(v, len, 0),
                 heap_sort(v + 1, len - 1)):
            NULL;
}

heap_sort(int v[], int len) 获取一个数组及其大小，并使用 heap_sort_step() 为数组中的每个成员构建最小堆，对其进行排序。这里需要尾调用。

heap_sort_step(int v[], int len, int i) 接受一个数组，它的大小和一个用于构建堆的索引，方程式如 nextl 和 nextr，2i+1 和2i+2，从 i = 0 开始。'bfl' 是一个优化技巧（相对于使用 ifs 的小改进）通过查看是否有更多项目来决定去哪个分支或只是 return 当前值先。 switch 使用 fallthrough 并且是构建堆的地方，3 和 2 表示右边有东西（0b11 和 0b10），1 表示左边有东西（0b01），默认行为是 returning当前号码。它曾经被写成：

int heap_sort_step(int v[], int len, int i){
    int nextl = (((i + 1) * 2) - 1), nextr = nextl + 1;
    if(nextl < len)
        while(v[i] > heap_sort_step(v, len, nextl))
            swap(v + i, v + nextl);

    if(nextr < len)
        while(v[i] > heap_sort_step(v, len, nextr))
            swap(v + i, v + nextr);

    return v[i];
}

至于递归这一步，就是将当前数与下一次函数调用的returning值进行比较，如果较大则交换，如果不是则进行级联return回根

在这一点上，我很确定这只是一个糟糕的实现，并且想知道这是否是由更改或其他原因造成的复杂性问题。是否可以使用相同的概念使其与归并排序和快速排序竞争？应该是O n(log(n))吧？

Answer 1

抛开递归的性能影响问题，以及您如何依赖 tail-call 优化来实现 heap_sort() 函数 non-recursive 毕竟，您的实现确实看起来不像堆排序。堆排序可以这样描述：

将待排序的元素排列成堆（天真地，O(n log n)；深思熟虑地，O(n)）
只要堆中至少有两个元素，(O(n)次迭代)
1. 将头元素与最后一个元素交换。 (O(1))
2. 将（逻辑）堆大小减少 1。(O(1))
3. 恢复堆状况。（O（log n）如果做对了）

当然，无论您是使用 max-heap 升序排序还是使用 min-heap 降序排序，这都适用。

正如您在评论中阐明的那样，您的方法是将数组排列成 min-heap 以获得最少的元素，然后重复数组的 n - 1 元素尾部。 这不是堆排序——它是选择排序的变体。如果well-implemented，则花费O(n²)，因为每个heap-building步至少要访问n / 2 non-leaf个节点，因此成本 O(n).

Answer 2

经过一些更改后，它就像一个魅力，这是解决方案：

不完整：

每个项目都会一遍又一遍地形成堆，因此，正如 John 所指出的，这就像一种奇怪的选择排序。

新增两个功能完成：

void sift(int v[], int len, int i){
    int nextl = 2 * i + 1, nextr = nextl + 1;
    int next  = 0;

    if(nextr < len)
        if(v[i] > v[nextr]){
            if(v[nextr] < v[nextl])
                swap(v + i, v + (next = nextr));
            else
                swap(v + i, v + (next = nextl));
        }
    if(nextl < len)
        if(v[i] > v[nextl])
            swap(v + i, v + (next = nextl));

    return (next == 0) ? NULL: sift_min(v, len, next);
}

恢复堆。在切换第一个和最后一个之后，它沿着一条路径沿着树向下交换每个较小的数字。

void reverse(int v[], int len){
    int i;
    for(i = 0; i < len/2; i++)
        swap((v + i), (v + (len - (i + 1))));
}

排序后反转数组，因为不知道第二步，使用最小堆，排序按降序进行，所以它只是为了使它升序。

主块中存在不必要的递归：

void heap_sort(int v[], int len){
    return (len > 1)?
                (heap_sort_step(v, len, 0),
                 heap_sort(v + 1, len - 1)):
            NULL;
}

被替换为

void heap_sort(int v[], int len){

    heapify(v, len, 0);//this is heap_sort_step with a new name

    int templen = len
    while(templen > 1){
        swap(v, v + --templen);
        sift(v, templen, 0);
    }

    reverse(v, len);
}

最终代码为：

void swap(int* ref1, int* ref2){
    int temp = *ref1;
    *ref1 = *ref2;
    *ref2 = temp;
}

int heapify(int v[], int len, int i){
    int nextl = 2 * i + 1, nextr = nextl + 1;

    if(nextr < len)
        while(v[i] > heapify(v, len, nextr))
            swap(v + i, v + nextr);

    if(nextl < len)
        while(v[i] > heapify(v, len, nextl))
            swap(v + i, v + nextl);

    return v[i];
}

void sift(int v[], int len, int i){
    int nextl = 2 * i + 1, nextr = nextl + 1;
    int next  = 0;

    if(nextr < len)
        if(v[i] > v[nextr]){
            if(v[nextr] < v[nextl])
                swap(v + i, v + (next = nextr));
            else
                swap(v + i, v + (next = nextl));
        }
    if(nextl < len)
        if(v[i] > v[nextl])
            swap(v + i, v + (next = nextl));

    return (next == 0) ? NULL: sift(v, len, next);
}

void reverse(int v[], int len){
    int i;
    for(i = 0; i < len/2; i++)
        swap((v + i), (v + (len - (i + 1))));
}

void heap_sort(int v[], int len){

    heapify(v, len, 0);

    int templen = len;

    while(templen > 1){
        swap(v, v + (--templen));
        sift(v, templen, 0);
    }

    reverse(v, len);
}

冗长，但它仍然以递归方式构建堆并且速度很快。可以使用 maxheap 更快，当然还可以消除递归。对于需要超过一分钟的相同样本，快速测试平均不到 0.1 秒。

仅使用递归构建最小堆

Building the min heap using recursion alone

c

optimization

recursion

heapsort

不完整：

主块中存在不必要的递归：