堆排序 - 堆（最小/最大）用于升序和降序排序？

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; 
    } 

奇特的是，它是有意义的，我认为 - 建立一个最小堆 - 提取分钟（或建立一个最小堆后在根执行最小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

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

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

如果要实现像

result.push_back(heap.pop_min()); 

你会得到您所期望的顺序。