0
0
Understanding the uses of Heaps in Data Structure
Heaps
A heap is a tree-based data structure in which all the nodes of the tree are in a specific order.
For example, if X is the parent node of Y, then the value of X follows a specific order with respect to the value of Y and the same order will be followed across the tree.
The maximum number of children of a node in a heap depends on the type of heap. However, in the more commonly-used heap type, there are at most 2 children of a node and it’s known as a Binary heap.
In binary heap, if the heap is a complete binary tree with N nodes, then it has smallest possible height which is log2N .
In the diagram above, you can observe a particular sequence, i.e each node has greater value than any of its children.
Suppose there are N Jobs in a queue to be done, and each job has its own priority. The job with maximum priority will get completed first than others. At each instant, we are completing a job with maximum priority and at the same time we are also interested in inserting a new job in the queue with its own priority.
So at each instant we have to check for the job with maximum priority to complete it and also insert if there is a new job. This task can be very easily executed using a heap by considering N jobs as N nodes of the tree.
As you can see in the diagram below, we can use an array to store the nodes of the tree. Let’s say we have 7 elements with values {6, 4, 5, 3, 2, 0, 1}.
Note: An array can be used to simulate a tree in the following way. If we are storing one element at index i in array Arr, then its parent will be stored at index i/2 (unless its a root, as root has no parent) and can be accessed by Arr[i/2], and its left child can be accessed by Arr[2∗i] and its right child can be accessed by Arr[2∗i+1]. Index of root will be 1 in an array.
There can be two types of heap: Max Heap: In this type of heap, the value of parent node will always be greater than or equal to the value of child node across the tree and the node with highest value will be the root node of the tree. Implementation: Let’s assume that we have a heap having some elements which are stored in array Arr. The way to convert this array into a heap structure is the following. We pick a node in the array, check if the left sub-tree and the right sub-tree are max heaps, in themselves and the node itself is a max heap (it’s value should be greater than all the child nodes) To do this we will implement a function that can maintain the property of max heap (i.e each element value should be greater than or equal to any of its child and smaller than or equal to its parent)
void max_heapify (int Arr[ ], int i, int N)
{
int left = 2*i //left child
int right = 2*i +1 //right child
if(left<= N and Arr[left] > Arr[i] )
largest = left;
else
largest = i;
if(right <= N and Arr[right] > Arr[largest] )
largest = right;
if(largest != i )
{
swap (Arr[i] , Arr[largest]);
max_heapify (Arr, largest,N);
}
}Example:
In the diagram below,initially 1st node (root node) is violating property of max-heap as it has smaller value than its children, so we are performing max_heapify function on this node having value 4.
As 8 is greater than 4, so 8 is swapped with 4 and max_heapify is performed again on 4, but on different position. Now in step 2, 6 is greater than 4, so 4 is swapped with 6 and we will get a max heap, as now 4 is a leaf node, so further call to max_heapify will not create any effect on heap. Now as we can see that we can maintain max- heap by using max_heapify function. Before moving ahead, lets observe a property which states: A N element heap stored in an array has leaves indexed by N/2+1, N/2+2 , N/2+3 …. upto N. Let’s observe this with an example: Lets take above example of 7 elements having values {8, 7, 6, 3, 2, 4, 5}.
So you can see that elements 3, 2, 4, 5 are indexed by N/2+1 (i.e 4), N/2+2 (i.e 5 ) and N/2+3 (i.e 6) and N/2+4 (i.e 7) respectively.
References
1. Earth, Hacker. “Heaps/Priority Queues Tutorials & Notes | Data Structures.” HackerEarth, HackerEarth, 12 Feb. 2021, www.hackerearth.com/practice/data-structures/trees/heapspriority-queues/tutorial/. Accessed 18 Oct. 2021.Continue…….
About Author
Vicky Chhetri
soluta fuga sed quidem id animi et ex velit et voluptas repellendus pariatur. illo omnis nihil iusto ut error blanditiis reiciendis nulla voluptate ut beatae perspiciatis voluptas. inventore non eaque autem voluptas debitis cum facere est omnis. accusamus saepe et molestiae cum vitae blanditiis natus temporibus molestiae quos molestiae possimus veniam aliquam.
facilis in voluptatem omnis ab vitae similique possimus non sed. perspiciatis voluptatem consequatur quod est pariatur excepturi alias omnis necessitatibus voluptatem.