Heap sort algorithm
Heapsort is also a comparison-based sorting algorithm. It arranges the elements of the unsorted array the same as we arrange in the insertion sort. The difference in this is that it arranges in the format of a sorted binary tree or a full binary tree. The arrangement starts from the back of the array. The time complexity for heap sort is O(nlogn) and the space complexity is O(1).
Topics Covered
- what is heap sort
- algorithm for heap sort
- C program to implement heap sort
- C++ program to implement heap sort
- Time and Space Complexity of heap sort
Algorithm for heap sort
1. Add the new element to the next available
position at the lowest level
2. Restore the max-heap property if violated
► General strategy is percolate up (or bubble up): if
the parent of the element is smaller than the
element, then interchange the parent and child.
OR
Restore the min-heap property if violated
► General strategy is percolate up (or bubble up): if
the parent of the element is larger than the
element, then interchange the parent and child.C program to implement heap sort
#include <stdio.h>
#include <conio.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");
}
// Driver code
int main() {
int arr[] = {1, 12, 9, 5, 6, 10};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array is \n");
printArray(arr, n);
}C++ program to implement heap sort
#include <iostream>
using namespace std;
// A function to heapify the array.
void MaxHeapify(int a[], int i, int n)
{
int j, temp;
temp = a[i];
j = 2*i;
while (j <= n)
{
if (j < n && a[j+1] > a[j])
j = j+1;
// Break if parent value is already greater than child value.
if (temp > a[j])
break;
// Switching value with the parent node if temp < a[j].
else if (temp <= a[j])
{
a[j/2] = a[j];
j = 2*j;
}
}
a[j/2] = temp;
return;
}
void HeapSort(int a[], int n)
{
int i, temp;
for (i = n; i >= 2; i--)
{
// Storing maximum value at the end.
temp = a[i];
a[i] = a[1];
a[1] = temp;
// Building max heap of remaining element.
MaxHeapify(a, 1, i - 1);
}
}
void Build_MaxHeap(int a[], int n)
{
int i;
for(i = n/2; i >= 1; i--)
MaxHeapify(a, i, n);
}
int main()
{
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
n++;
int arr[n];
for(i = 1; i < n; i++)
{
cout<<"Enter element "<<i<<": ";
cin>>arr[i];
}
// Building max heap.
Build_MaxHeap(arr, n-1);
HeapSort(arr, n-1);
// Printing the sorted data.
cout<<"\nSorted Data ";
for (i = 1; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}You can try the practical and visual representation of this topic on virtual labs.
