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).
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]]
}
}
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]]
}
}
Only getting the top element with O(1) time complexity (so very fast) is:
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 or Twitter, or check out my portfolio.
Top comments (0)