Binary heap sort algorithm performs the operation of sorting by using Binary tree. Binary trees are structure that is built out of elements in an array as shown in the form of a tree as shown in the below diagram. There are two types of binary heap tree, max-heap and min-heap.
Also its worth noting that there are other sorting algorithms such as Bubble sort, Selection sort, Insertion sort and Merge sort to sort elements in a given array.
When comes to Binary heap sort algorithm there are two types of it.
- A max heap Binary tree all in which parent nodes are either greater than or equal to each of its children nodes. The above shown heap tree is an example of Max heap tree.
- A min heap Binary tree in which all parent nodes are either smaller than or equal to each of its children nodes.
Heap sort performs sorting by removing the largest or smallest element among the nodes and putting it into the array. After each extraction, the heap is updated to maintain heap property. To explain this better take a look at the following example
Binary heap sort algorithm explanation:
Consider the following array with five numbers. We need to sort this in ascending order using Max-heap.
Let us construct a complete binary tree from the given array of numbers. The tree is constructed by arranging the elements in the array in such a way it forms a tree like data structure with parent and children nodes.
The tree needs to be a complete binary tree in order to be Heap data structure. There are two types of nodes, parent nodes and children nodes. Children nodes are the nodes which is attached to a single node which is the parent node for them. In the below Binary tree 15 is the parent node and 7 and 43 are its children node. Likewise in the next level of binary tree 7 is the parent node – 25 & 5 are the children nodes.
We need to compare the parent node with the children nodes ( 7, 25, 5).
Among which 25 is the largest.
7 will be swapped by 25 since it is greater than 7.
Compare the node 25 and 43 with its parent node 43.
15 will be replaced by 43 in the parent node since it is greatest of other two nodes in comparison.
Hence we get our Max-heap
Now we need to construct the sorted array. To do that there are three steps involved.
- Swap
- Remove
- Heapify
First swap the root node with the last node. Because we know that this is a Max-Heap so the root node is the largest among all and 5 is the smallest.
Remove the number 43
Reconstruct the heap by putting the largest value to the root node or Heapify
Swap 25 with 7
Remove 25
Heapify by putting 15 to the top
Swap 15 with 7
Remove 15
Swap 7 with 5
Remove 7
And we get the sorted array
And we get the sorted array
Steps to implement Binary heap sort Algorithm:
- Create a binary tree from the input elements
- You need to make it as a Max-Heap or Min-Heap based on the typing of sorting you need to perform.
- Compare the parent node with the children nodes
- Replace the parent node with the largest children node
- Do the same for all parent nodes
- Repeat until all the nodes in the binary tree are sorted and you get the max heap
- Then swap the root node with the last node
- Remove that node as this is the largest value and put that into the right most side of the array or left most side of the array depending on the sorting order
- Reconstruct the heap by putting the largest value to the root node or heapify
- Compare the root node with the right most child node
- Repeat the same process until all nodes are being sorted into the array
Sample code for Binary heap sort Algorithm:
#include <stdio.h>
// Function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// Main function to do heap sort
void heapSort(int arr[], int n) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Heap sort
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}
}
// Print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
// Main code
int main() {
int arr[] = {15, 7, 43, 25, 5};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array is \n");
printArray(arr, n);
}
Try this out:
- Take array of 6 elements and sort them in descending order using Binary tree sort algorithm.
Hope this tutorial helped you to understand Binary heap sort algorithm. Share your feedback, comments and queries in the comments section below. Check out other Algorithms and its explanation
