堆排序 - 哪个堆 (min/max) 用于升序和降序排序？

Question

我注意到一件非常奇怪的事情。

完成这个 lecture 后，我用 C++ 实现了一些堆排序代码。

代码如下。

    template<typename T> void min_heapify(std::vector<T> &vec, int i, int size)
    {
        int left  = (2*i); //left child of a zero-indexed heap (array)
        int right = (2*i)+1; //right child.
        int min;

        min = ( (left<size) && (vec[left] < vec[i]) ) ? left : i;
        min = ( (right<size) && (vec[right] < vec[min]) ) ? right : min;

        if (min!= i)
        {
            swapper(vec[i],vec[min]);
            min_heapify(vec, min, size);
        }
    }
    template<typename T> void build_min_heap(std::vector<T> &vec, int size)
    {
        int i = size/2;
        while(i--)
        {
            min_heapify(vec, i, size);

        }
    }
    template<typename T> void heap_sort(std::vector<T> &vec, int size)
    {
        // build min heap
        build_min_heap(vec, size);
        // then extract min repeatedly.
        while(size>0)
        {
            size--;
            swapper(vec[0],vec[size]);
            min_heapify(vec,0,size);
        }
    }

   int main()
   {
        vector<int> v{14,-1,1000, -999, 3,2,5,10};
        heap_sort(v, v.size());

        return 0;
   }

奇怪的是我觉得 - 建立一个最小堆 - 提取最小值（或在构建最小堆后在根目录执行 min-heapify）应该导致升序。然而，在执行这段代码并打印出结果向量之后，我得到：

1000 14 10 5 3 2 -1 -999

在试图理解发生了什么的同时，我改变了

min = ( (left<size) && (vec[left] < vec[i]) ) ? left : i;
min = ( (right<size) && (vec[right] < vec[min]) ) ? right : min;

到

min = ( (left<size) && (vec[left] > vec[i]) ) ? left : i;
min = ( (right<size) && (vec[right] > vec[min]) ) ? right : min;

实际上最终选择了父节点和子节点中较大的（或最大值），结果向量为：

-999 -1 2 3 5 10 14 1000

是我做错了什么还是我对heap/heap的理解有点不清楚？我在这里错过了什么？

Answer 1

是的swapper(vec[0],vec[size]);是提取。您正在将第一个元素提取到向量的最后一个元素中。因此得到相反的结果。

堆最小元素是 vec[0]。将其交换到最后一个位置将在该向量内创建从最大到最小的排序。

如果你实现类似

result.push_back(heap.pop_min());

您将得到您期望的顺序。

堆排序 - 哪个堆 (min/max) 用于升序和降序排序？

heap sort - which heap (min/max) to use for ascending and descending order sort?

c++

sorting

algorithm

heap

heapsort