0

免責事項として、私はこのサイトを初めて使用するため、質問の仕方がよくわかりません。これらの概念のいくつかがどのように機能するかを理解しようとしているだけなので、あまり厳しくしないでください。最初の段階で理解できていない場合は、そこから始めて、残りの時間を無駄にしないように、そのことを教えてください。ここでは何も行きません。私の理解に問題があるのではないかと思うので、さまざまな領域でヒープがどのように機能するかについていくつか質問を投げかけ、それらに答えようとしました。

まず、空のヒープに追加されたランダムな数値のセットがどのように見えるかを理解する手助けをしたいと思います。たとえば、9、4、5、3、2、7、8、7 があるとします。それをヒープに追加した後、ヒープはどのようになりますか? これは視覚的に理解できます（と思います）9はルート、4は最初の左の子などですが、これは具体的にはツリーではなく、ヒープであるため、番号を切り替えてソートしますかそれらを（「私の理解が正しければ」の段落を参照）、最小または最大の順序でソートされるようにしますか？

ここで、ヒープから 9 を削除したとします (9 がルートになると思います)。この変更にどのように対応し、次に何がルートに入れられるのでしょうか? ここで、9 がルートの場合、次に大きい数字を取得して 9 のスロットにコピーしますが、これが最小ヒープであり、下部のノードを削除するだけの場合は、削除されるだけです。問題。

同様に、配列内のヒープ項目の親を取得する式は何になるでしょうか? -- これは理解できたと思います。親が i の場合、左の子は i*2 で右の子は i*2+1 になります。したがって、親を見つけるには、親を見つけるために i/2 を割る必要があります。たとえば、i=7 の場合、親は i=3 になります。これは、3.5 が切り捨てられるためです。また、i=6 の場合、親も i=3 になります。この例から、i = 7 の子は i = 3 の右の子になり、i=6 は i = 3 の左の子になります。

これについての私の理解が正しければ、新しい用語がルートに追加された後に再ヒープするには、子を親と比較し、子が大きい場合は用語を切り替えます。しかし、2 つの子 (2 つある場合) を比較して、どちらが大きいかを確認し、どちらを交換する必要があるかを判断する必要があります。これは最大ヒープの場合であり、最小ヒープの場合は逆になります。

最後に、ルート要素をどこに追加するとしたら、どのように再ヒープするのでしょうか?

4

2 に答える 2

0

9 を削除すると、何もルートになりません。ヒープソート アルゴリズムは、並べ替えのために左の子 (4 と言った) に移動し、次に右の子 (または 5) などに移動します。番号がチェックされている場合はルート(実装が異なります)であり、4 がルートになり、5 になります。など。混乱している場合は、javascript で記述された次のヒープソートの定義を見てください。

var heapSort = function(array) {
  var swap = function(array, firstIndex, secondIndex) {
    var temp = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = temp;
  };
  var maxHeap = function(array, i) {
    var l = 2 * i;
    var r = l + 1;
    var largest;
    if (l < array.heapSize && array[l] > array[i]) {
      largest = l;
    } else {
      largest = i;
    }
    if (r < array.heapSize && array[r] > array[largest]) {
      largest = r;
    }
    if (largest !== i) {
      swap(array, i, largest);
      maxHeap(array, largest);
    }
  };
  var buildHeap = function(array) {
    array.heapSize = array.length;
    for (var i = Math.floor(array.length / 2); i >= 0; i--) {
      maxHeap(array, i);
    }
  };
  buildHeap(array);
  for (var i = array.length-1; i >= 1; i--) {
    swap(array, 0, i);
    array.heapSize--;
    maxHeap(array, 0);
  }
  array.heapMaximum = function(){
      return this[0];
  };
  array.heapExtractMax = function(){
      if(this.heapSize < 1){
          throw new RangeError("heap underflow");
      }
      var max = this[0];
      this[0] = this[this.heapSize - 1];
      this.heapSize--;
      maxHeap(this, 1);
      return max;
  };
  array.heapIncreaseKey = function(i, key){
      if(key < this[i]){
          throw new SyntaxError("new key is smaller than current key");
      }
      this[i] = key;
      while(i > 1 && this[Math.floor(i / 2)] < this[i]){
          swap(this, i, Math.floor(i / 2));
          i = Math.floor(i / 2);
      }
  };
  array.maxHeapInsert = function(key){
      this.heapSize--;
      this[this.heapSize] = -Infinity;
      this.heapIncreaseKey(this.heapSize, key);
  };
};
var a = [Math.floor(Math.random() * 100), Math.floor(Math.random() * 100), Math.floor(Math.random() * 100), Math.floor(Math.random() * 100), Math.floor(Math.random() * 100)];
heapSort(a);
document.writeln(a);
*{
  font-family:monospace;
}

実際にどのように回復するかはわかりませんが、スニペットを見て確認できます。

于 2015-03-28T00:33:13.603 に答える