Learning JavaScript Data Structures and Algorithms - Third Edition

The sift up operation

The code for the sift up operation is presented as follows:

siftUp(index) {
  let parent = this.getParentIndex(index); // {1}
  while (
      index > 0 &&
      this.compareFn(this.heap[parent], this.heap[index]) > Compare.BIGGER_THAN
    ) { // {2}
    swap(this.heap, parent, index); // {3}
    index = parent;
    parent = this.getParentIndex(index); // {4}
  }
}

The siftUp method receives the index of the inserted value. We also need to retrieve the index of its parent ({1}).

If the inserted value is smaller than its par­ent ({2} — in case of min heap or greater than its par­ent in case of the max heap), we swap the ele­ment with its parent ({3}). We will repeat this process until the root of the heap is also processed by updating the index and the ...