freeCodeCamp/curriculum/challenges/japanese/10-coding-interview-prep/data-structures/remove-an-element-from-a-max-heap.md

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
587d825b367417b2b2512c8b	最大ヒープから要素を削除する	1	301710	remove-an-element-from-a-max-heap

--description--

ヒープに要素を追加できるようになったので、要素を削除する方法を学びましょう。 要素の削除と挿入は、どちらも似たようなロジックが必要です。 最大ヒープでは一般に最大値を削除したいので、単に木の根からそれを抽出すれば良いのです。 これによって木のヒーププロパティが壊れるので、何らかの方法でそれを作り直す必要があります。 通常、最大ヒープの場合は次の方法でそれを行います。

1. ヒープ内の最後の要素を根の位置に移動します。
2. 根の子のいずれかが根より大きい場合は、根を、より大きい値の子と交換します。
3. 親が両方の子よりも大きくなるまで、または操作が木の最後のレベルに達するまで、交換を続けます。

--instructions--

手順: remove と呼ばれるメソッドを最大ヒープに追加してください。 このメソッドは、最大ヒープに追加された最大値を返し、ヒープから削除する必要があります。 また、ヒーププロパティが維持されるようにヒープの順序を変更する必要があります。 要素を削除した後、ヒープに残っている次の最大の要素が根になる必要があります。

--hints--

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

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

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

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

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

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

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

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

remove メソッドは max heap プロパティを維持しながら最大ヒープから最大要素を削除する必要があります。

assert(
  (function () {
    var test = false;
    if (typeof MaxHeap !== 'undefined') {
      test = new MaxHeap();
    } else {
      return false;
    }
    test.insert(30);
    test.insert(300);
    test.insert(500);
    test.insert(10);
    let result = [];
    result.push(test.remove());
    result.push(test.remove());
    result.push(test.remove());
    result.push(test.remove());
    return result.join('') == '5003003010';
  })()
);

--seed--

--seed-contents--

var MaxHeap = function () {
  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 below this line

  // Only change code above this line
};

--solutions--

// solution required