使用最小堆的堆排序算法

Question

当我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 

Answer 1

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

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

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

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

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