w3resource
Java Programming Exercies

Java Exercises: Heap sort Algorithm

Java Sorting Algorithm: Exercise-5 with Solution

Write a Java program to sort an array of given integers using Heap sort Algorithm.

In computer science, heapsort (invented by J. W. J. Williams in 1964) is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it interactively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort.

A run of the heapsort algorithm sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the heap property. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration.

Heapsort sorting

Animation credits : RolandH

Sample Solution:

Java Code:

import java.util.Arrays;
public class HeapSort {

    void HeapSort(int nums[]){
		buildheap(nums);
		for (int i = nums.length - 1; i >= 0; i--) {
			exchange(nums, i, 0);
			heap(nums, i, 0);
		}
	}

	private void exchange(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}

	private void heap(int[] nums, int size, int i) {
		int left = ((2 * i) + 1);  
		int right = ((2 * i) + 2);
		int max = i;

		if ((left < size) && (nums[left] > nums[i])) {
			max = left;
		}
		
		if ((right < size) && (nums[right] > nums[max])) {
			max = right;
		}

		if (max != i) {
			exchange(nums, i, max);
			heap(nums, size, max);
		}
	}

	private void buildheap(int[] nums) {
		for (int i = (nums.length / 2) - 1; i >= 0; i--) {
			heap(nums, (nums.length - 1), i);
		}
	}
	// Method to test above
    public static void main(String args[])
    {
        HeapSort ob = new HeapSort();
        int nums[] = {7, -5, 3, 2, 1, 0, 45};
        System.out.println("Original Array:");
        System.out.println(Arrays.toString(nums));
        ob.HeapSort(nums);
        System.out.println("Sorted Array");
        System.out.println(Arrays.toString(nums));
    }
}

Sample Output:

Original Array:
[7, -5, 3, 2, 1, 0, 45]
Sorted Array
[-5, 0, 1, 2, 3, 45, 7]

Flowchart:

Sort an array of given integers using the Heap sort Algorithm

Java Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Java program to sort an array of given integers using Merge sort Algorithm.
Next: Write a Java program to sort an array of given integers using Selection Sort Algorithm.

What is the difficulty level of this exercise?



New Content: Composer: Dependency manager for PHP, R Programming