Heaps in JavaScript (Part 2)

For this week, we are going to extend what we learned learn week by discussing more immediate fundamentals of Heap:

Bubble Up Part II

Now that we understand how to determine the relationship of elements with the internal heap, we’re ready to finish .bubbleUp().

In a min-heap, we need to ensure that every child is greater in value than its parent. Let’s add an element to the following heap.

console.log(minHeap.heap)
// returns [null, 10, 13, 21, 61, 22, 23, 99]

heap.add(12)

( new_element )
{ parent_element }
[null, 10, 13, 21, {61}, 22, 23, 99, (12)]

Oh no! We’ve violated the min-heap condition because 12‘s parent, 61, is greater than its child, 12.

To fix this, we will exchange the parent and the child elements.

before
[null, 10, 13, 21, {61}, 22, 23, 99, (12)]
SWAP 12 and 61
after
[null, 10, 13, 21, (12), 22, 23, 99, {61}]

12‘s parent is now 13 and it violates the min-heap condition. To fix this, we continue moving upwards swapping parent-child values.

before
[null, 10, {13}, 21, (12), 22, 23, 99, 61]
SWAP 12 and 13
after
[null, 10, (12), 21, {13}, 22, 23, 99, 61]

12‘s parent is now 10 and no longer violates the min-heap condition. We’ve restored the heap!

[null, {10}, (12), 21, 13, 22, 23, 99, 61]
The child, 12, is greater than the parent, 10!

Let’s recap our strategy for .bubbleUp():

Set the current element index to be the last index of heap
  While current element is valid and its value is less than its parent's value
   Swap the indexes
   Update the current element index to be its parent index

  class MinHeap {
  constructor() {
    this.heap = [ null ];
    this.size = 0;
  }

  add(value) {
    console.log(`.. adding ${value}`);
    this.heap.push(value);
    this.size++;
    this.bubbleUp();
    console.log(`added ${value} to heap`, this.heap);
  }

  bubbleUp() {
    let current = this.size;
    while (current > 1 && this.heap[current] < this.heap[getParent(current)]) {
      console.log('..', this.heap);
      console.log(`.. swap index ${current} with ${getParent(current)}`);
      this.swap(current, getParent(current));
      current = getParent(current);
    }
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

}

const getParent = current => Math.floor((current / 2));
const getLeft = current => current * 2;
const getRight = current => current * 2 + 1;

module.exports = MinHeap;

Removing the Min

Min-heaps would be useless if we couldn’t retrieve the minimum value. We’ve gone through a lot of work to maintain that value because we’re going to need it!

Our goal is to efficiently remove the minimum element from the heap. You’ll recall that we always locate the minimum element at index 1 (a placeholder element occupies index 0).

Our internal heap mirrors a binary tree. There’s a delicate balance of parent and child relationships we would ruin by directly removing the minimum.

console.log(minHeap.heap)
// [null, 10, 21, 13, 61, 22, 23, 99]
minHeap.popMin()
// 10
// [null, ???, 21, 13, 61, 22, 23, 99]

We need to remove an element that has no children, in this case, the last element. If we swap the minimum with the last element, we can easily remove the minimum from the end of the list.

[None, (10), 21, 13, 61, 22, 23, {99}]
minHeap.popMin()
SWAP minimum with last
[None, {99}, 21, 13, 61, 22, 23, (10)]
remove minimum
[None, 99, 21, 13, 61, 22, 23]
10

We removed the minimum element with minimal disruption. Unfortunately, our heap is out of shape again with 99 sitting where the minimum element should be. We will solve this in exercises to come…

class MinHeap {
  constructor() {
    this.heap = [ null ];
    this.size = 0;
  }

  popMin() {
    if (this.size === 0) {
      return null;
    }

    console.log(`\n.. Swap ${this.heap[1]} with last element ${this.heap[this.size]}`);
    this.swap(1, this.size);
    const min = this.heap.pop();
    this.size--;
    console.log(`.. Removed ${min} from heap`);
    console.log('..',this.heap);
    return min;

  }

  add(value) {
    console.log(`.. adding ${value}`);
    this.heap.push(value);
    this.size++;
    this.bubbleUp();
    console.log(`added ${value} to heap`, this.heap);
  }

  bubbleUp() {
    let current = this.size;
    while (current > 1 && this.heap[getParent(current)] > this.heap[current]) {
      console.log('..', this.heap);
      console.log(`.. swap index ${current} with ${getParent(current)}`);
      this.swap(current, getParent(current));
      current = getParent(current);
    }
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

}

const getParent = current => Math.floor((current / 2));
const getLeft = current => current * 2;
const getRight = current => current * 2 + 1;

module.exports = MinHeap;