April 2018
Beginner to intermediate
426 pages
10h 19m
English
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 parent ({2} — in case of min heap or greater than its parent in case of the max heap), we swap the element with its parent ({3}). We will repeat this process until the root of the heap is also processed by updating the index and the ...