Heap sort is a comparison-based sorting algorithm and divides the input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.
Heap sort is not stable sorting. A heap sort is especially efficient for data that is already stored in a binary tree. Heap sort does not take any extra space.
Write a program to implement heap sort.
source Code
package com.dsacode.Algorithm.sorting; public class HeapSort { private int heapsize; public HeapSort(){ heapsize =0; } int left(int i){ return (2*i); } int right(int i){ return (2*i+1); } int parent(int i){ return (i/2); } void MaxHeapify(int A[], int i){ int largest,temp,l,r; l=left(i); r=right(i); if( A[l] > A[i] && l <= heapsize) largest=l; else largest=i; if( A[r] > A[largest] && r <= heapsize) largest=r; if(largest!=i){ temp=A[i]; A[i]=A[largest]; A[largest]=temp; MaxHeapify(A,largest); } } void buildmaxheap(int A[], int n){ heapsize=n; for(int i=n/2; i>=1;i--) MaxHeapify(A,i); } void heapsort(int A[], int n){ int temp; buildmaxheap(A,n); for(int i=n;i>=2;i--){ temp=A[i]; A[i]=A[1]; A[1]=temp; heapsize--; MaxHeapify(A,1); } } public static void main(String[] args) { int []arr=new int[20]; arr[1]=12; arr[2]=34; arr[3]=56; arr[4]=23; arr[5]=45; arr[6]=78; arr[7]=99; System.out.print("Unsorted array before sorting : [" ); for(int i=1; i <= 7; i++){ if(i==7) System.out.print(arr[i] +"]"); else System.out.print(arr[i] +","); } System.out.println(); HeapSort obj = new HeapSort(); obj.heapsort(arr,7); System.out.print("Sorted array After Heap sorting :["); for(int i = 1; i <= 7; i++){ if(i == 7) System.out.print(arr[i] +"]"); else System.out.print(arr[i] +","); } } }
Output
Unsorted array before sorting: [12, 34, 56, 23, 45, 78, 99] Sorted array After Heap sorting: [12, 23, 34, 45, 56, 78, 99]
Algorithm Explanation
![]() | Construct a heap using the array of elements. |
![]() | Add each item to heap and MaxHeapify when inserting into the heap. |
![]() | When all items have been added, remove them one by one. The topmost item is stored in an array. |
![]() | Sorted elements stored in an array. |
Time Complexity
Best Case | Average Case | Worst Case |
---|---|---|
O(n log(n)) | O(n log(n)) | O(n log(n)) |