Heap Sort Algorithm

Data structures are one of the most important topics in computer science. It is defined as the management, organization, storage of data so that we can access the data effectively and modify it however we want. The main important types of data structures are Arrays, Linked Lists, Stacks, Queues, Trees, Heaps, and Graphs. Heaps are a special case of binary trees.

And in the data structures, the sorting techniques are very important. sorting means arranging the data either in ascending order or descending order according to the wish of the user. there are many sorting techniques in the data structures and the important ones are Bubble Sort, Quick Sort, Merge Sort, Selection Sort, Insertion Sort, and Heap Sort. Every technique uses a different type of approach and sorts the data structures.

Want to read this story later? Save it in Journal.

Heapsort is one of the important sorting techniques every student should know. It mainly involves the building of heaps from the data. the knowledge of heaps can also help us in memory management. So in this blog, we are gonna discuss how to build heaps and using heap sort and uses of it.

Building a Heap

Heap building is very easy. Consider you are given an array with N elements in it. Now make a binary tree from the given array i.e, add the elements to the nodes. the order of adding is

First the parent node, then the child node at left, then the child node at right. For example, given an array = { 4, 3, 7, 1, 8, 5 }. The corresponding heap is:

after arranging into a binary tree we have two choices. Either make it a Max Heap or Min Heap.

Max Heap

In this, the value of the parent node is always greater than the child nodes. we swap the elements and make the Max Heap.

Min Heap

In this, the value of the parent node is always less than the child nodes. we swap the elements and make the Mix Heap.

for example, consider an array arr[] = { 2, 5, 4, 8, 9, 10, 11}. Then the Max Heap is:

The pseudo-code for the max heap is:

void build_heap (int arr[ ];int n)
{
for(int i = n/2–1 ; i >= 0; i- -)
{
down_heapify (arr, i, n);
}
}

(Here down_heapify is an inbuilt function). Similarly, you can also make Min Heap. The time complexity for building a heap is O(N) and the function down_heapify has a complexity of O(log N).

Some functions of the heap

• Insert: It is used to add the elements into the heap.
• Remove: It is used to delete the elements from the heap.
• Find Minimum/Maximum: In many problems, we are asked to find the largest or smallest element. So we use this function.
• Decrease/Increase Key: The key determines the place in the heap where the node will be. By using this function we can adjust the node and perform operations.
• Merge: The merge function is used when we are required to combine two heaps into a single heap.

Heap Sort Algorithm

After making the heap into a max heap or min-heap, now we can apply the sorting algorithm.

The process is to take out the max element from the heap and then again heapify the tree so that the second largest element will be now at the root node of the tree and continue the process until all elements are taken out.

The steps in the Heap sort are:

1. Create a heap from the elements of the array.
2. Convert the heap into a Max heap.
3. Now swap the element in the root node i.e, the maximum element with the last element of the heap i.e, the element present in the leaf node.
4. Now remove the swapped element from the leaf node.
5. Hepify the tree again so that the 2nd largest element is now in the root node.
6. Continue steps 3, 4, 5 until all the elements are taken out from the tree.

The reason we swap with the last element i.e, the leaf node is that we can only perform the deletion of elements in a tree only at root nodes. So we always swap the elements needed to be removed with leaf nodes and delete them.

For example, take an array arr[] = { 11, 9, 10, 8, 5, 2, 4}

As you can see we swap the max elements with leaf node and delete them one by one and we get the sorted output.

The pseudo-code is:

void heap_sort(int arr[], int n) {

build_heap(arr);

for(int i = n-1; i >= 1; i- -) {

swap(arr[i], arr[0]);

down_heapify(arr, 0, i+1);

}

}

(Here build_heap, down_heapify, swap are inbuilt functions used)

The time complexity of this code is O(N log N) as we heapify the heap N-1 times. the complexity of building the would be O(N) and down_heapify function would be O(log N).

Some application of Heap data structure and Heap Sort

1. The heap data structure is mainly used in priority queues.
2. It is also used in Prim’s algorithm.
3. It is used in Dijkstra’s algorithm.
4. The Heap Sort is used in problems like sorting a nearly sorted or K sorted array.
5. To find the K largest or smallest numbers present in an array.

Dijkstra’s algorithm

The main aim of this algorithm is to find the shortest distance between any two nodes in a graph or to find the distance from the source node to any other node of the graph by producing a shortest-path tree.

This algorithm has applications in GPS for finding the shortest distance and path between your current location and destination. It is also used in industries that use modeling networks.

How the algorithm works

You select one node and start from that node(Source Node) and the algorithm finds the distance between the source node and all the other nodes in the graph. it notes the shortest distance and updates the value when it finds a shorter path. once it finds the shortest distance it marks that path and marks that node as visited. this continues till all the shortest paths of all nodes are found. So finally we can find the shortest path between any two nodes.

Conclusion

Heapsort is a very important algorithm in data structures that has a lot of real-life applications like finding the shortest path which is used in airline traffic systems. The algorithm is not so complicated, easy to use but is better to use only for the given applications. Because if we use this sorting technique for other problems, the algorithm works but has high time complexity relative to the other techniques that can be used.

📝 Save this story in Journal.