Building a GitHub account x 100 days of code: Day 8
Today’s Goal: Heaps and Priority Queue
In the ocean of sorting and searching techniques, heaps and priority queues have stood the test of time, carving out niche use cases in which they prove to be far more valuable than other data structures and techniques.
Like trees, heaps are arranged in nodes that are connected with others in a well-defined pattern — and are classified as min or max heaps. The difference between the two is how they are arranged with respect to each other.
In min heaps, the parent node is less than or equal to its children nodes. This means that the root node is the lowest value amongst the values in the data structure and the further down you go, the larger the values will get. In max heaps, the root node is the largest among the values and the value of the node decreases as you go further down the data structure. These are both very useful implementations for accessing the minimum/maximum value in constant time. However, to understand its use cases, like all other data structures, it is important to analyze its insert and delete operations.
Heaps are best used in statistical applications when trying to find the nth largest or smallest value, which are DSA problems that come along more often than you think; and next time it does — consider implementing a heap.
If you have been following so far, the concepts of priority queues are actually very straightforward. It refers to an implementation in which elements are assigned a certain priority and dequeued in a particular order. This is useful in scheduling problems when there is a clear demarcation of priority in the usage of resources.
Priority queues are not a data structure, but rather an abstraction of a datatype. This means that it is more of a conceptual idea that you can implement using a data structure — and one way to do that is using heaps. In fact, a heap is a great choice to execute the concept of priority queues since all the priority queue operations are most efficient with heaps.
Todays’s questions I found were the most practical so far and pushed me to think of the most efficient way to approach problems.
Tomorrow I will be advancing to graphs, a concept that is more foreign to me than most others so far (finger-crossed).
