Heap sort
Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to the selection sort where we first find the minimum element and place the minimum element at the beginning. Repeat the same process for the remaining elements.
Working of Heap Sort algorithm:
To understand heap sort more clearly, let’s take an unsorted array and try to sort it using heap sort. Consider the array: arr[] = {4, 10, 3, 5, 1}.
Build Complete Binary Tree: Build a complete binary tree from the array.
Build complete binary tree from the array
Transform into max heap: After that, the task is to construct a tree from that unsorted array and try to convert it into max heap.
- To transform a heap into a max-heap, the parent node should always be greater than or equal to the child nodes
- Here, in this example, as the parent node 4 is smaller than the child node 10, thus, swap them to build a max-heap.
- Transform it into a max heap
- Now, as seen, 4 as a parent is smaller than the child 5, thus swap both of these again and the resulted heap and array should be like this:
Make the tree a max heap
Perform heap sort: Remove the maximum element in each step (i.e., move it to the end position and remove that) and then consider the remaining elements and transform it into a max heap.
- Delete the root element (10) from the max heap. In order to delete this node, try to swap it with the last node, i.e. (1). After removing the root element, again heapify it to convert it into max heap.
- Resulted heap and array should look like this:
Remove 10 and perform heapify
- Repeat the above steps and it will look like the following:
Remove 5 and perform heapify
- Now remove the root (i.e. 3) again and perform heapify.
Remove 4 and perform heapify
- Now when the root is removed once again it is sorted. and the sorted array will be like arr[] = {1, 3, 4, 5, 10}.
The sorted array
Introduction to Sorting Techniques – Data Structure and Algorithm Tutorials
Sorting refers to rearrangement of a given array or list of elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.
When we have a large amount of data, it can be difficult to deal with it, especially when it is arranged randomly. When this happens, sorting that data becomes crucial. It is necessary to sort data in order to make searching easier.
Contact Us