Exploring the heap data structure 
Tags: javascript, algorithms
Published: 2021-02-05 14:42:45

While going through some new resources about coding interviews and algorithms I found a way to efficiently prioritize a to-do list using a heap data structure. 

#Heap

This data structure is like a binary tree since it has parent nodes and leaf nodes. However, the order is different since it orders the values of the nodes from top to bottom (ascending `Min Binary Heap` or descending `Max Binary Heap`), while binary trees order nodes on left(less than parent) and right(more than parent).

![Wikipedia Max Binary Heap](https://upload.wikimedia.org/wikipedia/commons/c/c4/Binary_Heap_with_Array_Implementation.JPG)

Heaps are also called PriorityQueues because that is the main implementation of having a top element that has been sorted based on its priority or value. The most common implementation methods of a heap class are to: 

* Insert a new element into the correct position or 
* Remove the top priority value from it and reorganize the heap by priority

These two methods have a [Big O time complexity](https://dev.to/santispavajeau/managing-big-o-notation-3162) of `O(log n)`, but only retrieving the top priority element without extracting it is `O(1)`. For search, the heap is slower `O(n)` so it's not the best algorithm at finding elements in all the data set, binary search is faster at this. The space complexity is `O(n)` since it only stores the array representation of the heap.

## The method to insert a new element

With the general information sorted out, let's get into the details.

```javascript
export class MinBinaryHeap{
    constructor(){
        this.heapArray = []
    }

    insertElement(newElement){
        this.heapArray.push(newElement)

        let newElementId = this.heapArray.length - 1 

        while(newElementId > 0){ // while this id is still in the bounds of the heap array
            let newElementParentId = Math.floor((newElementId -1) /2)
            let newElementParent = this.heapArray[newElementParentId]

            if(newElementParent > newElement){
                this.swapHelper(newElementParentId, newElementId) // swap elements (found by id on this.heapArray)
                newElementId = newElementParentId // swap ids in this while loop scope
                // console.log(this.heapArray)
            }else{
                break
            }
        }
    }

    swapHelper(parentId, leafId){
        [this.heapArray[parentId], this.heapArray[leafId]] = [this.heapArray[leafId], this.heapArray[parentId]]
    }
}
```

In a few words, we are comparing the leaf element to the parent element, so if the parent is larger the elements are swapped since it's a `Min Binary Heap`. The way the parent index is found is by dividing `Math.floor((leafIndex -1)/2)`, because the [representation of the heap in an array follows this condition](https://www.tutorialspoint.com/array-representation-of-binary-heap#:~:text=The%20complete%20binary%20tree%20that,ordering%20is%20called%20binary%20heap.&text=min%20Heap%20is%20the%20heap,of%20min%20heap%20is%20smallest.). This representation in an array allows for the insert method to be `O(log n)` because the index is being divided in half every iteration until it reaches 0.

## The method to return the top priority element and rearrange the heap

Again in a few words in this method, we pull out the top priority item and set the new top priority item. So after the top item is shot out of the heap values array, the last item becomes the first, but now the heap is out of order so it needs to be rearranged. So to rearrange the heap we visit each leaf and compare their values and the lowest becomes the new parent. We also have to make sure the leaves currently exist and also make sure to only swap the leaf that has the lowest value.

``` javascript
 export class MinBinaryHeap{
    constructor(){
        this.heapArray = []
    }

    pullTopElementAndReorder(){
        let topElement = this.heapArray[0]

        if(this.heapArray.length < 1) return null

        this.heapArray[0] = this.heapArray[this.heapArray.length - 1]
        this.heapArray.pop()

        this.reorderHelper()

        return topElement
    }

    reorderHelper(){
        let parentId = 0
        let leftLeafId = (parentId * 2) + 1
        let rightLeafId =  (parentId * 2) +2
        let leftLeaf = this.heapArray[leftLeafId]
        let rightLeaf = this.heapArray[rightLeafId]
        let parent = this.heapArray[parentId]

        while(!!leftLeaf && !!rightLeaf || !!leftLeaf){ //while both leaves exist or only the left leaf


            let minLeaf = Math.min(leftLeaf, rightLeaf)
            if( minLeaf < parent){ // if either one of the two leaves is less than parent swapHelper

                if(minLeaf === leftLeaf){
                    this.swapHelper(parentId, leftLeafId) // swapHelper values
                    parentId = leftLeafId // swap ids to move on down the heap
                }

                if(minLeaf === rightLeaf) {
                    this.swapHelper(parentId,rightLeafId)
                    parentId = rightLeafId
                }
            } else break

            leftLeafId = (parentId * 2) + 1
            rightLeafId =  (parentId * 2 ) + 2

            leftLeaf = this.heapArray[leftLeafId]
            rightLeaf = this.heapArray[rightLeafId]
            parent = this.heapArray[parentId]
        }
    }

    swapHelper(parentId, leafId){
        [this.heapArray[parentId], this.heapArray[leafId]] = [this.heapArray[leafId], this.heapArray[parentId]]
    }
}
```

Only getting the top element with `O(1)` time complexity (so very fast) is:

``` javascript
    getTop(){ // O(1)
        return this.heapArray[0]
    }
```

# Prioritizing todos

Now that the `Heap` or `PriorityQueue` is implemented we can just sort our data based on a value of our choice. Then use the methods to add new todos to the queue or to finish a task and take it out of the queue.

A react implementation is in the upcoming blog.

Feel more than welcome to reach out with any ideas/comments at [Linkedin](https://www.linkedin.com/in/santiago-salazar-pavajeau/) or [Twitter](https://twitter.com/santispavajeau), or check out my [portfolio](https://www.santiagosalazarpavajeau.live).