Heap Data Structure is a special Tree-based data structure that is a complete binary Tree. In Heap Structure all node are in a specific order.
A number of children of a node generally depends on the type of heap. However, for the most common implementation every node has two children and this is known as a Binary Heap. When dealing with heaps we generally talk about min heap and max heap.
Min Heap: A Min Heap is a special type of Binary Heap in which the value of 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 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 do we define the structure of heap and how do we store data. Since 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 initialised 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 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 s smaller, than swap it with its parent.
- Continue the process until either the new elements parent is smaller than or equal to the new element or the new element reaches the root.
For removing an element from Min-Heap perform the following:
- Place the root element in a variable to return later
- Remove the least 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.
Applications
Heap Sort: Heaps can be sued to sort an array of elements in a specific order inefficient time complexity of O (NlogN). If we want to sort the elements in a heap in descending order we can use max Heap. Call the build function for the array elements and now top of the tree contains the maximum element. We will swap this element with the last element and build heap again until we get all the elements in their correct position.
Priority Queue: Priority Queue is one of the most useful applications of Heaps. There are similar to queue but the difference is in the logical order we use to insert and delete an element. Every number has some priority assigned to it and element with the highest priority will be moved to the front of the queue and low priority element will be moved at the back. Priority queue has further applications such as:
- CPU Scheduling
- Implementing Dijkstra’s Algorithm , Prim’s MST
- When data is transferred asynchronously between two processes
Let us look at some basic implementations of priority queue in C++ Standard Template Library and Java.
In case of Java if we want to pop and return the latest element in the queue we use poll() but if we want to return only and not pop an item from queue we use peek(). To add an element we can use push(data) or emplace_back(data) in C++.This will add data to the top of a priority queue. In the case of Java, we can use add(data) method.
To explore more topic, click here.
By Mridul Kumar
