A Heap is a specific kind of Binary Tree called Complete Binary Tree, arranged in a specific order. In this article, I'm gonna tell you what exactly we mean by a "Heap", different kinds of heaps and their applications.
What is Heap Data Structure?
It is a Complete Binary Tree which is arranged in an order that depends on the type of heap that you're using. Let's first elaborate on the "complete binary tree" part.
What is a Complete Binary Tree?
Binary tree is a kind of Tree data structure which has only two child nodes. A Complete binary tree means that each node (except for the nodes at the lowest level and the leaf nodes) should have both their children.
Note that the tree should be checked for being full from left to right side on all the levels. If any spot is empty on the left side while being full on the right side on the same level, then the tree will not be considered a complete binary tree.
Visually, such a structure should look something like this - 
An example of a Binary Tree not being complete -
Types of Heap
Heaps are of two types based on the order in which the elements are arranged in it - Min Heap and Max Heap .
Min Heap
It is a type of Complete Binary Tree in which smallest element becomes the root node, followed by larger elements in succeeding levels. Each level contains element smaller than the level succeeding it.
In other words, for each parent node, the child nodes must have value greater than its parent node.
View Website
View Website
View Website
While inserting, if the child node comes out to be smaller than parent node, swapping should be done between them.
The process should look something like this - 
Max Heap
Like min heap, it is just another type of complete binary tree but with opposite characteristics from that of a min heap. That is, each parent node should have a value greater than their child nodes. so the first level(root node) should have the maximum value and the last level(the leaf nodes) should have the smallest values present in the array of numbers.
So, while inserting, if any child node ends up getting a parent node with value smaller than itself, then swapping should be done between them.
The process looks like this - 
Applications of Heaps
Priority Queues
Priority queue concept can be implemented via various data structures like avl-trees. But, it can be done with the least complexity through heaps.
Heap sort
It is a sorting algorithm which is done with the help of heap data structure. Elements are deleted one by one from the root node end of the heap until no element is left in the heap. The type of heap(max or min) determines the order in which elements of the final array would be arranged in.
Used in process scheduling in Operating System
It is somewhat like a priority queue. The processes with a higher priority should be kept at the topmost position, followed by lower priority tasks and the last level should contain the lowest priority task.
This helps the OS in finalizing which task to run for a specific interval of time.
Basically, you can make use of this data structure whenever quick access to the maximum or minimum element is required. It is also used in algorithms like Dijkstra's shortest path algorithm, Huffman Coding and Prim's algorithm as these algorithms require the use of Priority Queues.
Conclusion
Heaps are very useful data structures and come handy in many algorithms as listed above. That's why a good knowledge on heaps is very important. Its implementation is somewhat similar to a binary tree.
I hope you liked reading this article. You can find more such informative articles on data structures here.
Thanks for reading!😉
Comments (0)