GeezerVison is showing github.com — Java/Programs/HeapSort.java at main · arshcoder13/Java

Expand file tree

HeapSort.java

Copy path

More file actions

Latest commit

History

68 lines (56 loc) · 1.94 KB

HeapSort.java

Copy path

File metadata and controls

68 lines (56 loc) · 1.94 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

public class HeapSort {

public void sort(int arr[]) {

int n = arr.length;

// Build heap (rearrange array)

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

// One by one extract an element from heap

for (int i = n - 1; i > 0; i--) {

// Move current root to end

int temp = arr[0];

arr[0] = arr[i];

arr[i] = temp;

// call max heapify on the reduced heap

heapify(arr, i, 0);

}

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap

void heapify(int arr[], int n, int i) {

int largest = i; // Initialize largest as root

int l = 2 * i + 1; // left = 2*i + 1

int r = 2 * i + 2; // right = 2*i + 2

// If left child is larger than root

if (l < n && arr[l] > arr[largest])

largest = l;

// If right child is larger than largest so far

if (r < n && arr[r] > arr[largest])

largest = r;

// If largest is not root

if (largest != i) {

int swap = arr[i];

arr[i] = arr[largest];

arr[largest] = swap;

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);

}

/* A utility function to print array of size n */

static void printArr(int arr[]) {

int n = arr.length;

for (int i = 0; i < n; ++i){

System.out.print(arr[i] + " ");

}

System.out.println();

}

public static void main(String[] args) {

int arr[] = { 4, 23, 6, 78, 1, 54, 231, 9, 12 };

int n = arr.length;

System.out.println("The original Heap sort is: ");

printArr(arr);

HeapSort heapSort = new HeapSort();

heapSort.sort(arr);

System.out.println("The sorted array is");

printArr(arr);

}