堆排序-使用哪个堆（最小/最大）进行升序和降序排序？

Question

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

读完这节课后，我在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堆-提取min（或在构建min堆后在根目录下执行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 

我是否做错了什么，或者我对堆/堆排序的理解不清楚？我错过了什么？

Answer 1

是<代码>交换程序（vec[0]，vec[size]） 是提取。将第一个元素提取到向量的最后一个元素。因此得到了相反的结果。

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

如果你实施类似

result.push_back(heap.pop_min());

你会得到你期待的订单。