Files

camperbot 5c868af2b8 chore(i18n,learn): processed translations (#44851 )

2022-01-20 20:30:18 +01:00

6.2 KiB

Raw Permalink Blame History

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
587d825a367417b2b2512c8a	要素を最大ヒープに挿入する	1	301703	insert-an-element-into-a-max-heap

--description--

次に、別のツリーデータ構造である二分ヒープに進みます。二分ヒープは、ヒーププロパティを満たす、部分的に順序付きの二分木です。ヒーププロパティは、親ノードと子ノードの関係を指定します。最大ヒープ (すべての親ノードがその子ノード以上であるようなヒープ)、または最小ヒープ (その逆であるヒープ) を持つことができます。二分ヒープは完全な二分木でもあります。つまり、木のすべてのレベルが完全に埋まっています。最後のレベルが部分的に埋まっている場合には、左から右に埋まります。

二分ヒープは、左右の参照を含むノードを持つツリー構造として実装できますが、ヒーププロパティに従って部分的に順序付けすれば、配列を使ってヒープを表現することができます。ここでは親子関係に注目します。あらゆる親ノードの子と、あらゆる子ノードの親を、簡単な算術で計算することができます。

例えば、二分最小ヒープを次のような配列で表現することを考えてみましょう。

[ 6, 22, 30, 37, 63, 48, 42, 76 ]

根ノードは最初の要素、6 です。根ノードの子は 22 と 30 です。これらの値の配列インデックス間の関係を見てみると、i の子要素は 2 * i + 1 および 2 * i + 2 です。同様に、インデックス 0 にある要素は、インデックス 1 と 2 にある 2 つの子の親です。より一般的には、Math.floor(i - 1) / 2) を使用すれば、任意のインデックスにあるノードの親を見つけることができます。二分木がどれほど大きくなってもこれらのパターンが当てはまります。最後に、配列内の最初の要素をスキップするというわずかな調整で、この演算をさらに簡単にできます。これを行うと、与えられたインデックス i にある任意の要素に対して次のような関係が作られます。

配列表現の例:

[ null, 6, 22, 30, 37, 63, 48, 42, 76 ]

要素の左の子: i * 2

要素の右の子: i * 2 + 1

要素の親: Math.floor(i / 2)

この計算を理解してしまえば、配列表現を使うことは非常に便利です。なぜなら、子ノードへの参照を維持する必要がないので、この演算でノード位置が素早く決まり、メモリ使用量が減少するからです。

--instructions--

手順: ここでは最大ヒープを作成してください。まず、ヒープに要素を追加する insert メソッドを作成します。挿入中は、ヒーププロパティを常に維持することが重要です。つまり最大ヒープの場合、根要素は常に木の中で最大値を持ち、すべての親ノードは子ノードより大きくなければなりません。ヒープの配列実装では、通常、これは次の 3 つのステップで実行されます。

配列の末尾に新しい要素を追加します。
要素が親より大きい場合は、それらを交換します。
新しい要素が親より小さくなるまで、または木の根に到達するまで、交換を続けます。

最後に、ヒープに追加されたすべての要素の配列を返す print メソッドを追加します。

--hints--

MaxHeap データ構造が存在する必要があります。

assert(
  (function () {
    var test = false;
    if (typeof MaxHeap !== 'undefined') {
      test = new MaxHeap();
    }
    return typeof test == 'object';
  })()
);

MaxHeap に insert というメソッドが必要です。

assert(
  (function () {
    var test = false;
    if (typeof MaxHeap !== 'undefined') {
      test = new MaxHeap();
    } else {
      return false;
    }
    return typeof test.insert == 'function';
  })()
);

MaxHeap に print というメソッドが必要です。

assert(
  (function () {
    var test = false;
    if (typeof MaxHeap !== 'undefined') {
      test = new MaxHeap();
    } else {
      return false;
    }
    return typeof test.print == 'function';
  })()
);

insert メソッドは最大ヒーププロパティに従って要素を追加する必要があります。

assert(
  (function () {
    var test = false;
    if (typeof MaxHeap !== 'undefined') {
      test = new MaxHeap();
    } else {
      return false;
    }
    test.insert(50);
    test.insert(100);
    test.insert(700);
    test.insert(32);
    test.insert(51);
    test.insert(800);
    const result = test.print();
    const solution = JSON.stringify([null,800,51,700,32,50,100]);
    const solutionWithoutNull = JSON.stringify([800,51,700,32,50,100]);

    return (result.length == 6) ? (JSON.stringify(result) == solutionWithoutNull) : (JSON.stringify(result) == solution);
  })()
);

--seed--

--seed-contents--

var MaxHeap = function() {
  // Only change code below this line

  // Only change code above this line
};

--solutions--

var MaxHeap = function() {
    // Only change code below this line
    this.heap = [];
    this.parent = index => {
      return Math.floor((index - 1) / 2);
    }
    this.insert = element => {
      this.heap.push(element);
      this.heapifyUp(this.heap.length - 1);
    }
    this.heapifyUp = index => {
      let currentIndex = index,
      parentIndex = this.parent(currentIndex);
      while (currentIndex > 0 && this.heap[currentIndex] > this.heap[parentIndex]) {
        this.swap(currentIndex, parentIndex);
        currentIndex = parentIndex;
        parentIndex = this.parent(parentIndex);
      }
    }
    this.swap = (index1, index2) => {
      [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }
    this.print = () => {
      return this.heap;
    }
    // Only change code above this line
};

6.2 KiB Raw Permalink Blame History