Heaps | Javascript | Part-6.3

Introduction article to the data structure. Heap concept with practical examples applied to the Javascript language.

Are you looking to improve your fundamental knowledge of computer science, especially data structure and algorithms? Then you’re in the right place. Let’s go through some common data structures and implement them in JavaScript.

Heap Tree

Heaps are another type of tree that have some particular rules. A heap is essentially used to get the highest priority element at any point in time. There are two types of heaps, based on the heap property — MinHeap and MaxHeap.

MinHeap: The parent node is always less than the child nodes.
MaxHeap: The parent node is always greater than or equal to the child nodes.

Max Heap

Min Heap

In this data structure, there’re no guarantees between siblings, meaning that nodes at the same “level” don’t follow any rule besides being higher/lower than their parent.

Also, heaps are as compact as possible, meaning each level contains all the nodes it can contain with no empty spaces, and new children are put into the left spaces of the tree first.

Heaps, and in particular binary heaps, are frequently used to implement priority queues, which at the same time are frequently used in well-known algorithms such as Dijkstra’s path-finding algorithm.

Priority queues are a type of data structure in which each element has an associated priority and elements with a higher priority are presented first.

Why do we need something like Heaps?

Heaps are primarily used for getting the minimum or the maximum value present in a heap in O(1) time. Linear data structures like Arrays or LinkedList can get you this value in O(n) time while non-linear data structures like Binary Search Trees(BST) can get you this value in O(log n) time where n is the number of elements.

Here’s the time complexity of various operations performed on a heap with n elements:
Access the min/max value: O(1)
Inserting an element: O(log n)
Removing an element: O(log n)

Heaps make it blazing fast to access the priority-level elements. The Priority Queue data structure is implemented using Heaps. As the name suggests, you can access elements on a priority basis in O(1) time using a Priority Queue. It is commonly used in Dijkstra’s Algorithm, Huffman Coding. Don’t worry if you don’t know these algorithms yet! We’ll cover them in detail in the next set of articles.

Heaps help in quicker access to the min/max elements. Got it! But why do we need these elements in the first place?

Here are some of the real-world use cases of Heaps:

1. The Operating System uses heaps for scheduling jobs on a priority basis.
2. The producer-consumer model can be implemented using heaps to let consumer access the higher-priority elements first. It is used in the implementation of the Blocking Priority Queue.
3. Other applications include Order Statistics to find the kth-smallest/kth-largest element in an Array, in HeapSort Algorithm, and Graph Algorithms such as Djiktra’s to find the shortest path, and Prim’s minimal spanning tree algorithm.

Try writing the code for MaxHeap on your own. It should not be difficult, you just have to tweak a few if conditions.

Leetcode Questions list related to tree
https://leetcode.com/problemset/all/?page=1&topicSlugs=heap-priority-queue

Some Solved Leetcode questions related to the Tree. Please have a look so you have a clear picture of your mind about the Tree data structure.

Leetcode Solutions | Platform for learning to code

Recent Articles if you guys want to checkout

Binary Tree | Javascript | Part-6.2

Tree | Javascript | Part-6.1

Hash Table | Javascript | Part-5

In this blog, I have tried to collect & present the most important points to consider when building Javascript / Node.js applications, feel free to add, edit, comment, or ask.
I recommend you to go over the references for more details. Happy coding!