Heap sort

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