Applications of Heap Data Structure

Complete Binary Tree

A complete binary tree is a binary tree that satisfies the following conditions.

• Each node may have no more than two children.
   
• All the levels should be filled except for the last one. The last level may or may not be filled.
   
• All the nodes should be filled from left to right. 

For example, the tree in the first image is not a complete binary tree because the node "F" is not filled from left to right. The second image is a complete binary tree.

Let us now recall the heap data structure.

Also Read, Prefix Sum Array , hash function in data structure

Heap Data Structure

A heap is a complete binary tree in which nodes are ordered differently depending on whether it is a max-heap or a min-heap.

Min Heap: The value at each node should be smaller than its children. The root node stores the minimum value.

Max Heap: The value at each node should be greater than its children. The root node in the max heap stores the maximum value.

You can read this article to learn more about heap.

Now, let's learn about the applications of the heap data structure.

Applications of the Heap Data Structure

You can use the heap data structure whenever you need to retrieve the largest or smallest element. The heap allows easy retrieval of these elements because they will always be present at the tree's root node. The accessing of elements from the root of a tree has a time complexity of O(1). Remember that the rest of the array elements in your heap generally remain unsorted. Hence, quick retrieval is guaranteed only for the minimum or the maximum element.
 

Following are some of the applications of the heap data structure.

1. Heap is used in the construction of priority queues. Using a priority queue, we can insert, delete, identify the highest priority element, or insert and extract with priority, among other things, in O(log N) time. Although data structures such as the BST (Binary Search Tree), AVL (Adelson-Velsky and Landis) trees, and the Red-Black tree can accomplish the same functionalities, they are more complex than heaps.
   
   A real-life example of the use of priority queues This type of queue could be used when customers who take a short time to serve are given priority instead of those who arrive early. For example, customers with a small bill to pay may be given precedence at a licensing center. The average waiting time for all clients in the queue can be reduced due to this.
    
2. The priority queues implemented using heap data structure have more advanced uses in graph algorithms. These include prims, Dijkstra's algorithm, Huffman coding, and the BFS algorithm.
    
3. You can use the heap data structure to find the kth smallest / largest element in an array quickly and effectively. You can go through this article to learn more about the problem.
    
4. Heap Sort is used in systems concerned with security and embedded systems, such as the Linux Kernel.
    
5. An efficient and straightforward sorting algorithm, the heap sort algorithm uses the heap data structure. Heap sort is a robust in-place sorting algorithm whose time complexity, in the worst case, is O(nlogn).

Min Heap: 

A Min Heap is a special type of Binary Heap in which the value of the parent node is smaller than or equal to its children and root value is the smallest value in a sequence of numbers. Let us consider a task of N jobs where every job has its own priority and we are supposed to complete jobs in increasing order of priority, i.e. smallest priority first. Now we are supposed to do these jobs according to the priority and also at the same time add new jobs with their own priority.

This task can be done easily considering the sequence of jobs as N nodes of a tree. Making a min heap out of these sequences of jobs will have handled the functioning in an efficient manner. The basic operations to be performed are mentioned below.

• Inserting a value
• Extracting the minimum value
• Removing values

A Min Heap can perform all these operations in a very efficient manner in O(LogN) time complexity. Let us see how we define the structure of the heap and how we store data. Since the heap is a binary tree defining a structure isn’t that difficult.

At the vertex, we store the data and we have left and right pointers which are initialized to NULL in case a child doesn’t exist. We use an array to hold data. Store the root at position one (not using 0-based indexing). Now for any node at a position we have

• Its left the child at 2i
• Its right child at 2i+1
• Its parent (if any) at i/2 (integer division)

For inserting an element into a Min-Heap from an array of numbers perform the following

• Place the new element in the next available position in the array.
• Compare the new element with its parent (if any). If the new element is smaller, then swap it with its parent.
• Continue the process until either the new element parent is smaller than or equal to the new element or the new element reaches the root.

To remove an element from Min-Heap perform the following:

• Place the root element in a variable to return later
• Remove the last element in the deepest level and move it to the root.
• While the moved element has value greater than at least one of its children swap this value with smaller values child.
• Return the original root that was saved.

Let us look at the C++ implementation of the Min Heap. We will first build a function that will make sure that the tree maintains the heap property. It’s called the heapify function.

Time Complexity – O(LogN): Let implement the build function and then we will run the min_heapify function on remaining nodes other than leaf nodes.

Time Complexity – O(N): In the above function it is worth noting that elements indexed from N/2 +1 to N are leaf nodes and are 1 element heaps. Hence we start calling our function from N/2.

Max Heap: 

It is similar to min Heap the only difference here being that the parent has a value greater than its children and the root node is the maximum value in a sequence of number. Here also we will be using the max_heapify function and build function to build the max heap. Let’s assume that we have a heap having some elements which are stored in array arr. We pick a node in the array, check if the left sub-tree and the right sub-tree are maxing heaps, in themselves and the node itself is a max heap (its value should be greater than all the child nodes).

Here also the time complexity for building the Heap is O(N) while max_heapify function takes O(LogN) time.

Let us now answer some frequently asked questions.

Also read - Data Structure MCQ

Frequently Asked Questions

What is heap data structure?

A heap is a complete binary tree in which nodes are ordered differently depending on whether it is a max-heap or a min-heap.

What is the time complexity of inserting an element into the heap?

The time complexity of inserting a new element into the heap is O (log n). 

When do we use heap?

You can use the heap data structure when you need to fetch the largest or smallest element quickly. You can use the min-heap or max-heap accordingly.

How do we differentiate between a tree and a graph?

Trees and graphs are different since there can never be loops in a tree, but we can have loops in a graph. Also, all the nodes in a tree are always connected, but that is not true for a graph.

What is a priority queue?

Every value has some priority associated with it in a priority queue. We dequeue the value with the highest priority first.

Conclusion

In this article, we have discussed various applications of the heap data structure. To learn more about the heap, refer to these articles.

• Implementation of Heap
• Time Complexity of building a heap
• Binary Heap
• N-ary Heap
• Heap Sort for Decreasing Order Using Min-Heap
• Application of Priority Queue

You can also consider our Online Coding Courses such as the DSA in Python, C++ DSA Course, DSA in Java Course to give your career an edge over others.

Happy Learning, Ninjas!