Data Structures for Coding Interviews in JavaScript/

...

/

Max Heap (Implementation)

Max Heap (Implementation)

Let's implement a max heap!

We'll cover the following...

Max Heap: Skeleton Code #

Let’s start with some function declarations for the heap class.

The __percolateUp() function is meant to restore the heap property going up from a node to the root.

The __maxHeapify() function restores the heap property starting from a given node down to the leaves.

The two underscores before the __percolateUp() and __maxHeapify() functions imply that these functions should be treated as private functions.

Press + to interact
class maxHeap {
    constructor() {
    }
    insert(val) {}
    getMax() {}
    removeMax() {}
  
    __percolateUp(index) {}
  
    __maxHeapify(index) {}
}
var heap = new maxHeap()

Implementing the constructor #

The constructor will initialize an array that will contain the values of the heap. It will also store the number of elements currently present in the heap.

Press + to interact
class maxHeap {
    constructor() {
      this.heap=[];
      this.elements = 0;
    }
    insert(val) {}
    getMax() {}
    removeMax() {}
  
    __percolateUp(index) {}
  
    __maxHeapify(index) {}
}
var heap = new maxHeap()

Implementing the insert() function

This function appends the given value to the heap array and calls the __percolateUp() function on it. This function will swap the values at parent-child nodes until the heap property is restored. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed and/or swapped.

Although our heap grows uniformly i.e. on every new insert, we can increase the size of heap by 1. We can do this because the push method of the array is O(1) in JavaScript. However, when deleting elements from the heap, we do not resize the heap array as the time complexity of splice or slice methods, used for this purpose in JavaScript, is O(n). This is the reason we keep the count of elements in the heap so that if later on, we can reuse the space already present in heap array, we are able to use it.

Press + to interact
class maxHeap {
    constructor() {
      this.heap=[];
      this.elements = 0;
    }
    insert(val) {
      if (this.elements >= this.heap.length){
            this.elements = this.elements + 1
            this.heap.push(val);
            this.__percolateUp(this.heap.length - 1);
         }
        else{
            this.heap[this.elements] = val;
            this.elements = this.elements + 1
            this.__percolateUp(this.elements - 1);
        }
    }
    getMax() {}
    removeMax() {}
  
    __percolateUp(index) {}
  
    __maxHeapify(index) {}
}
var heap = new maxHeap()

Implementing the getMax() function

This function returns the maximum value in the heap which is the root, i.e., the first value in the array. It does not modify the heap itself. The time complexity of this function is in O(1)O(1) constant time. This is what makes heaps so special!

Press + to interact
class maxHeap {
    constructor() {
         this.heap = [];
         this.elements = 0;
     }
     insert(val) {
         if (this.elements >= this.heap.length){
            this.elements = this.elements + 1
            this.heap.push(val);
            this.__percolateUp(this.heap.length - 1);
         }
        else{
            this.heap[this.elements] = val;
            this.elements = this.elements + 1
            this.__percolateUp(this.elements - 1);
        }
     }
     getMax() {
         if (this.elements != 0)
             return this.heap[0]
         return null;
     }
    removeMax() {}
  
    __percolateUp(index) {}
  
    __maxHeapify(index) {}
}
var heap = new maxHeap()

Implementing the removeMax() function

This function removes and returns the maximum value in the heap.

It first checks if the number of elements in the heap is greater than 1 if it is so, it saves the maximum value in a variable, swaps the maximum value with the last leaf, deletes it, and restores the max heap property on the rest of the tree by calling the __maxHeapify() function on it. The function then checks if the heap is of size 1. If it is, it saves the maximum value in the tree (the only value really) in a variable, deletes it, and returns it. Then it checks if the heap is empty and returns null if it is.

The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed and/or swapped.

Press + to interact
 class maxHeap {
     constructor() {
         this.heap = [];
         this.elements = 0;
     }
     insert(val) {
         if (this.elements >= this.heap.length){
            this.elements = this.elements + 1
            this.heap.push(val);
            this.__percolateUp(this.heap.length - 1);
         }
        else{
            this.heap[this.elements] = val;
            this.elements = this.elements + 1
            this.__percolateUp(this.elements - 1);
        }
     }
     getMax() {
         if (this.elements != 0)
             return this.heap[0]
         return null;
     }
     removeMax() {
         if (this.elements > 1) {
             var max = this.heap[0]
             this.heap[0] = this.heap[this.elements - 1]
             this.elements = this.elements - 1
             this.__maxHeapify(0)
             return max
         } else if (this.elements == 1) {
             var max = this.heap[0]
             this.elements = this.elements - 1
             return max
         } else {
             return null;
         }
     }
    __percolateUp(index) {}
    __maxHeapify(index) {}
}
var heap = new maxHeap()

Implementing the __percolateUp() function

This function restores the heap property by swapping the value at a parent node if it is less than the value at a child node. After swapping, the function is called recursively on each parent node until the root is reached. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed and/or swapped.

Press + to interact
 class maxHeap {
     constructor() {
         this.heap = [];
         this.elements = 0;
     }
     insert(val) {
         if (this.elements >= this.heap.length){
            this.elements = this.elements + 1
            this.heap.push(val);
            this.__percolateUp(this.heap.length - 1);
         }
        else{
            this.heap[this.elements] = val;
            this.elements = this.elements + 1
            this.__percolateUp(this.elements - 1);
        }
     }
     getMax() {
         if (this.elements != 0)
             return this.heap[0]
         return null;
     }
     removeMax() {
         if (this.elements > 1) {
             var max = this.heap[0]
             this.heap[0] = this.heap[this.elements - 1]
             this.elements = this.elements - 1
             this.__maxHeapify(0)
             return max
         } else if (this.elements == 1) {
             var max = this.heap[0]
             this.elements = this.elements - 1
             return max
         } else {
             return null;
         }
     }
     __percolateUp(index) {
         var parent = Math.floor( (index - 1) / 2)
         if (index <= 0)
             return
         else if (this.heap[parent] < this.heap[index]) {
             var tmp = this.heap[parent]
             this.heap[parent] = this.heap[index]
             this.heap[index] = tmp
             this.__percolateUp(parent)
         }
     }
     __maxHeapify(index) {}
 }
 var heap = new maxHeap()

Implementing the __maxHeapify() function

This function restores the heap property after a node is removed. It swaps the values of the parent nodes with the values of their largest child nodes until the heap property is restored. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed and/or swapped.

Press + to interact
 class maxHeap {
     constructor() {
         this.heap = [];
         this.elements = 0;
     }
     insert(val) {
         if (this.elements >= this.heap.length){
            this.elements = this.elements + 1
            this.heap.push(val);
            this.__percolateUp(this.heap.length - 1);
         }
        else{
            this.heap[this.elements] = val;
            this.elements = this.elements + 1
            this.__percolateUp(this.elements - 1);
        }
     }
     getMax() {
         if (this.elements != 0)
             return this.heap[0]
         return null;
     }
     removeMax() {
         if (this.elements > 1) {
             var max = this.heap[0]
             this.heap[0] = this.heap[this.elements - 1]
             this.elements = this.elements - 1
             this.__maxHeapify(0)
             return max
         } else if (this.elements == 1) {
             var max = this.heap[0]
             this.elements = this.elements - 1
             return max
         } else {
             return null;
         }
     }
     __percolateUp(index) {
         var parent = Math.floor( (index - 1) / 2)
         if (index <= 0)
             return
         else if (this.heap[parent] < this.heap[index]) {
             var tmp = this.heap[parent]
             this.heap[parent] = this.heap[index]
             this.heap[index] = tmp
             this.__percolateUp(parent)
         }
     }
     __maxHeapify(index) {
         var left = (index * 2) + 1;
         var right = (index * 2) + 2;
         var largest = index;
         if ((this.elements > left) && (this.heap[largest] < this.heap[left])) {
             largest = left
         }
         if ((this.elements > right) && (this.heap[largest] < this.heap[right]))
             largest = right
         if (largest != index) {
             var tmp = this.heap[largest]
             this.heap[largest] = this.heap[index]
             this.heap[index] = tmp
             this.__maxHeapify(largest)
         }
     }
 }
var heap = new maxHeap()
heap.insert(12)
heap.insert(10)
heap.insert(-10)
heap.insert(100)
console.log(heap.getMax())
heap.removeMax()
console.log(heap.getMax())

Building a max-heap

Let’s build a max-heap now. Suppose we have nn elements in an array which represents our heap. For every node to be positioned in accordance ...