ヒープソート - 昇順と降順の並べ替えに使用するヒープ（最小/最大）

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()); 

のようなものを実装する場合はあなたが期待していた順序を取得します。