7

当我heapsort使用 a实现时min-heap，它会从最大到最小对数组进行排序。这是heapsortusing所需的输出min-heap吗？排序完成后再次排序以输出最小到最大似乎是多余的，因为它heap本身具有最小到最大的结构。

代码：

#include <iostream>
#include <vector>
#include "random.h"
#include "print.h"
int parent(int i)
{
    return (i - 1) / 2;
}
int left(int i)
{
    if(i == 0)
        return 1;
    else
        return 2*i;
}
int right(int i)
{   if(i == 0)
        return 2;
    else
        return 2*i + 1;
}
void min_heapify(std::vector<int> &A, int i, int heapsize)
{
    int smallest;
    int l = left(i);
    //std::cout << "left = " << l << std::endl;
    int r = right(i);
    //std::cout << "right = " << r << std::endl;
    if(l <= heapsize && A[l] < A[i])
        smallest = l;
    else
        smallest = i;
    //std::cout << "smallest = " << smallest << std::endl;
    if(r <= heapsize && A[r] < A[smallest])
        smallest = r;
    if(smallest != i) {
        print(A);
        exchange(A, i, smallest);
        min_heapify(A, smallest, heapsize);
    }
}
void build_min_heap(std::vector<int> &A)
{
    int heapsize = A.size() - 1;
    for(int i = (A.size() - 1) / 2; i >= 0; i--)
        min_heapify(A, i, heapsize);
}
void heapsort(std::vector<int> &A)
{
    int heapsize = A.size() - 1;
    build_min_heap(A);
    std::cout << "heapsort after buildmaxheap" << std::endl;
    print(A);
    for(int i = A.size() - 1; i > 0; i--) {
        exchange(A, 0, i);
        heapsize--;
        std::cout << "heapsize = " << heapsize << std::endl;
        min_heapify(A, 0, heapsize);
    }
}
int main()
{
    std::vector<int> B;
    fill(B, 5);
    print(B);
    heapsort(B);
    print(B);
    return 0;
}

代码输出：

41 65 31 41 19 
41 65 31 41 19 
41 65 19 41 31 
41 19 65 41 31 
41 19 31 41 65 
19 41 31 41 65 
heapsort after buildmaxheap
19 31 41 41 65 
heapsize = 3
65 31 41 41 19 
31 65 41 41 19 
heapsize = 2
heapsize = 1
65 41 41 31 19 
heapsize = 0
65 41 41 31 19

20 个元素的输出：

41 65 31 41 19 15 72 11 78 69 37 23 29 63 75 4 5 49 75 99 
after buildmaxheap
4 5 15 11 19 23 29 41 31 69 37 41 72 63 75 65 78 49 75 99 
after sort
99 78 75 75 72 69 65 63 49 41 41 37 31 29 23 19 15 11 5 4
4

3 回答 3

6

Order：使用 max-heapify 升序排序， min-heapify 降序排序。

排序：使用 min-heapify 构建堆不会对数组进行排序；它只强制执行（较弱的）最小堆属性，即

A[parent(i)] <= A[i]

i对于除根以外的每个节点。堆建立后，根（数组中最左边的位置）具有最小元素。然后排序重复地将元素从根向右移动并在根上调用 min-heapify （将剩余的最小部分带到那里），因此是降序。

您发布的代码一目了然，但无法按原样编译，因此我无法测试。如果您的数组在构建堆后立即出现排序，那应该是巧合。尝试更大的测试。

于 2013-09-20T17:38:50.420 回答
2

通常您使用最大堆按升序排序，因为它更容易。使用最大堆，您将最大值“浮动”到前面，并从后面构建排序列表。

如果要使用最小堆按升序排序，则必须向后构建。（即最低的是最后一个索引）。否则你会搅动你的堆。

start 18 70 6 13 12 55 
min-heap(backwards) -> 18 70 55 13 12 6
then
swap  6 w 18 -> 6, 70 55 13 12 18 -> sink 18 -> 70 55 13 18 12
swap 12 w 70 -> 6 12, 55 13 18 70 -> sink 70 -> 55 70 18 13
swap 13 w 55 -> 6 12 13, 70 18 55 -> sink 55 -> 70 55 18
swap 18 w 70 -> 6 12 13 18, 55 70 -> sink 70 -> 70 55
swap 55 w 70 -> 6 12 13 18 55, 70 
done
于 2013-09-20T17:37:28.540 回答
2

我只是想知道这个问题（堆排序最后是否有额外的步骤，不必要的元素交换。只需使用 min-heaps 并调用min-heapify并完成您的工作）。

关于这种方式，我们可以实现 O(logn) 时间，这在一定程度上使二叉决策树模型不合格——这表明 O(nlogn) 是比较排序算法可接受的最严格上限。

简短的回答是：堆数据结构不是二叉搜索树。堆可以保证元素以从上到下排序的方式排序，但是二叉搜索树也保证它们也会从左到右排序。我们只是混合了二叉树和堆。

最小堆只保证，

Amin[Parent]<=A[either_of_the_children] // says nothing about ordering of children

这是一棵二叉树（尽管不平衡且未排序）：

二叉树

这是一个堆：

最小堆

希望你明白我的意思。如果仍然没有，那么可以将其想象为，一个最小堆表示一个数组，保证父级小于其子级，但没有说明所有子级是否按从左到右的排序顺序排列？我们仍将对当前根的每个子节点执行 min-heapify 以进行交换。

于 2015-05-13T12:32:47.543 回答