Heap sort Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the minimum element and place the minimum element at the beginning. We repeat the same process for the remaining elements.
The process of reshaping a binary tree into a Heap data structure is known as heapify. A binary tree is a tree data structure that has two child nodes at max. If a nodes children nodes are heapified, then only heapify process can be applied over that node. A heap should always be a complete binary tree.
Starting from a complete binary tree, we can modify it to become a Max-Heap by running a function called heapify on all the non-leaf elements of the heap. i.e. heapify uses recursion.
Example :
Algorithm - Heap sort
Algorithm heap sort [A (0..n-1)]
// Sort a given array by heap sort.
// Input : An array A(0,n-1) of orderable elements.
// Output : Array A [0,n-1] sorted in non- decreasing order .
heapify(array)
Root = array[0]
Largest =largest( array[0] ,array [2 *0 + 1]. array[2 * 0 + 2])
if(Root != Largest)
Swap(Root, Largest)
Following are the implementation of Heap sort into programs
#include < stdio.h >
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i)
{
int left, right, largest;
largest = i;
left = 2 * i + 1;
right = 2 * i + 2;
// Check if left child exists and is larger than its parent
if (left < n && arr[left] > arr[largest])
largest = left;
// Check if right child exists and larger than its parent
if (right < n && arr[right] > arr[largest])
largest = right;
// if root is not the largest
if (largest != i) {
swap(&arr[i], &arr[largest]); //make root the largest
heapify(arr, n, largest); // Apply heapify to the largest node
}
}
void heap_sort(int arr[], int n)
{
int i;
for (i = (n / 2) - 1; i >= 0; i--)
heapify(arr, n, i);
for (i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]); //Move the largest element at root to the end
heapify(arr, i, 0); //Apply heapify to reduced heap
}
}
int main()
{
int arr[] = { 20, 13, 34, 56, 12, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
heap_sort(arr, n);
printf("\nAfter performing Heap Sort:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Code
import java.util.Scanner;
public class HeapSort{
private static int N;
public static void sort(int arr[]){
heapMethod(arr);
for (int i = N; i > 0; i--){
swap(arr,0, i);
N = N-1;
heap(arr, 0);
}
}
public static void heapMethod(int arr[]){
N = arr.length-1;
for (int i = N/2; i >= 0; i--)
heap(arr, i);
}
public static void heap(int arr[], int i){
int left = 2*i ;
int right = 2*i + 1;
int max = i;
if (left <= N && arr[left] > arr[i])
max = left;
if (right <= N && arr[right] > arr[max])
max = right;
if (max != i){
swap(arr, i, max);
heap(arr, max);
}
}
public static void swap(int arr[], int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
Scanner in = new Scanner( System.in );
int n;
System.out.println("Enter the number of elements to be sorted:");
n = in.nextInt();
int arr[] = new int[ n ];
System.out.println("Enter "+ n +" integer elements");
for (int i = 0; i < n; i++)
arr[i] = in.nextInt();
sort(arr);
System.out.println("After sorting ");
for (int i = 0; i < n; i++)
System.out.println(arr[i]+" ");
System.out.println();
}
}
Code
# heapify
def heapify(arr, n, i):
largest = i # largest value
l = 2 * i + 1 # left
r = 2 * i + 2 # right
# if left child exists
if l < n and arr[i] < arr[l]:
largest = l
# if right child exits
if r < n and arr[largest] < arr[r]:
largest = r
# root
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # swap
# root.
heapify(arr, n, largest)
# sort
def heapSort(arr):
n = len(arr)
# maxheap
for i in range(n, -1, -1):
heapify(arr, n, i)
# element extraction
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
# main
arr = [2,5,3,8,6,5,4,7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
print (arr[i],end=" ")
Code
Sample Output
Before sorting array
4 3 6 2 5 8 5 7
Sorted array is
2 3 4 5 5 6 7 8
Time Complexity
best case, average case, worst case
Visualized
Note: For better Visualized Understanding visit our algorithm Visualizer
