DEV Community

Santiago Salazar Pavajeau
Santiago Salazar Pavajeau

Posted on

Exploring the heap data structure

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

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 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.

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]]
    }
}
Enter fullscreen mode Exit fullscreen mode

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. 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.

 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]]
    }
}
Enter fullscreen mode Exit fullscreen mode

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

    getTop(){ // O(1)
        return this.heapArray[0]
    }
Enter fullscreen mode Exit fullscreen mode

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 or Twitter, or check out my portfolio.

Top comments (0)