Heap sort is a comparison-based sorting algorithm. It divides the input into a sorted and an unsorted region. It iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.
Write a program to implement the heapsort
Algorithm Explanation
![]() | Construct an array using unsorted elements. Pass to the utility function. |
![]() | Build the heap tree using unsorted elements. |
![]() | The heapify procedure used for building a heap from the bottom up by successively shifting downward to establish the heap property. |
![]() | Start deletion operations, storing each deleted element at the end of the heap array. Remove highest priority item from heap (largest) |
![]() | Reform heap with remaining data and display the sorted array. |
Source Code
package com.dsacode.DataStructre.priorityqueue; public class HeapSortImpl { private int heapsize; public HeapSortImpl() { 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[] array = new int[20]; array[1] = 45; array[2] = 45; array[3] = 9; array[4] = 89; array[5] = 34; System.out.print("Before Sorting: "); for (int i = 1; i <= 5; i++) System.out.print(array[i] + " "); System.out.println(); HeapSortImpl obj = new HeapSortImpl(); obj.heapsort(array, 5); System.out.print("After Sorting: "); for (int i = 1; i <= 5; i++) System.out.print(array[i] + " "); } }
Output
Before Sorting: 45 45 9 89 34 After Sorting: 9 34 45 45 89