最小のヒープソートを実装してk番目の最小要素を見つける方法は？

Question

私はクラスの選択ソート問題を実装しており、割り当ての1つは最小ヒープを使用して配列のk番目に小さい要素を見つけることです。私は何の問題も作成していない（ルート）のk倍

グループ

で戻りk番目の最小の要素

• が配列
• が最小を削除heapify：私は手順がある知っています最小のヒープ。私はちょうど最小のk回を適切に削除し、グループのk番目の最小の要素を正常に返す方法についてはわかりません。これまでのところ、私が今までに持っているものは次のとおりです。

  bool Example::min_heap_select(long k, long & kth_smallest) const { 
  //duplicate test group (thanks, const!) 
  Example test = Example(*this); 
  
  //variable delcaration and initlization 
  int n = test._total ; 
  int i; 
  
  //Heapifying stage (THIS WORKS CORRECTLY) 
  for (i = n/2; i >= 0; i--) { 
      //allows for heap construction 
      test.percolate_down_protected(i, n); 
  }//for 
  
  
  //Delete min phase (THIS DOESN'T WORK) 
  for(i = n-1; i >= (n-k+1); i--) { 
  
  
      //deletes the min by swapping elements 
      int tmp = test._group[0]; 
      test._group[0] = test._group[i]; 
      test._group[i] = tmp;  
  
      //resumes perc down 
      test.percolate_down_protected(0, i);   
  
  
  }//for 
  
      //IDK WHAT TO RETURN 
      kth_smallest = test._group[0]; 
  
  
  
  void Example::percolate_down_protected(long i, long n) { 
  
  //variable declaration and initlization:  
  int currPos, child, r_child, tmp; 
  currPos = i; 
  tmp = _group[i]; 
  child = left_child(i); 
  
  //set a sentinel and begin loop (no recursion allowed) 
  while (child < n) { 
  
      //calculates the right child's position 
      r_child = child + 1; 
  
      //we'll set the child to index of greater than right and left children 
      if ((r_child > n) && (_group[r_child] >= _group[child])) { 
       child = r_child; 
      } 
      //find the correct spot 
      if (tmp <= _group [child]) { 
       break; 
      } 
  
      //make sure the smaller child is beneath the parent 
      _group[currPos] = _group[child]; 
  
      //shift the tree down 
      currPos = child; 
      child = left_child(currPos); 
  } 
  
  //put tmp where it belongs 
  _group[currPos] = tmp; 
  } 
  

  前述したように、最小ヒープ部分は正しく機能します。私は何をすべきか理解しています。ルートk回を削除するのは簡単ですが、その後、配列内のどのインデックスが返されますか？0？これはほとんど動作します.k = nかk = 1で価値がありません。k番目の最小要素がAnyのヘルプにあると大いに感謝します！

Answer 1

ユーザーにとって意味のある配列インデックスは、最小要素であるゼロだけです。したがって、k要素を除去した後、k番目の最小要素は0になります。

おそらく、ヒープを破棄して、ヒープ自体について心配するようにユーザーに依頼するのではなく、値を返す必要がありますが、割り当ての詳細はわかりません。

C++標準ライブラリには、make_heap,pop_heap、およびnth_elementの助けとなるアルゴリズムがあります。