Java Program to Implement Heap Sort

This is the Java Program to Implement Heap Sort Using Library Functions.

Problem Description

Given an array of integers, sort the array using heapsort algorithm, as built into the library.

Problem Solution

The idea is to create a priority queue of the array elements. A priority queue is a min-heap. Extract the elements from the priority queue one by one and store them in the array. The array obtained will be sorted.

Program/Source Code

Here is the source code of the Java Program to Implement Heap Sort Using Library Functions. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

  1.  
  2. //Java Program to Implement Heap Sort Using Library Functions
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.InputStreamReader;
  6. import java.util.Arrays;
  7. import java.util.PriorityQueue;
  8.  
  9. public class HeapSortLib {
  10.     // Function to implement heapsort using priority queue
  11.     static void libraryHeapSort(int[] array){
  12.         PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
  13.         int i;
  14.         for(i=0; i<array.length; i++){
  15.             priorityQueue.add(array[i]);
  16.         }
  17.         i=0;
  18.         while(!priorityQueue.isEmpty()){
  19.             array[i++] = priorityQueue.poll();
  20.         }
  21.     }
  22.     // Function to read user input
  23.     public static void main(String[] args) {
  24.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  25.         int size;
  26.         System.out.println("Enter the size of the array");
  27.         try {
  28.             size = Integer.parseInt(br.readLine());
  29.         } catch (Exception e) {
  30.             System.out.println("Invalid Input");
  31.             return;
  32.         }
  33.         int[] array = new int[size];
  34.         System.out.println("Enter array elements");
  35.         int i;
  36.         for (i = 0; i < array.length; i++) {
  37.             try {
  38.                 array[i] = Integer.parseInt(br.readLine());
  39.             } catch (Exception e) {
  40.                 System.out.println("An error Occurred");
  41.             }
  42.         }
  43.         System.out.println("The initial array is");
  44.         System.out.println(Arrays.toString(array));
  45.         libraryHeapSort(array);
  46.         System.out.println("The sorted array is");
  47.         System.out.println(Arrays.toString(array));
  48.     }
  49. }
Program Explanation

1. The function libraryHeapSort(), a priority queue is created.
2. The loop for(i=0; i<array.length; i++), adds the enemy elements to the priority queue.
3. The loop while(!priorityQueue.isEmpty()) extracts the elements from priority queue one by one and then adds them to the queue.

advertisement
advertisement

Time Complexity: O(n*log(n)) where n is the number of elements in the array.

Runtime Test Cases
 
Case 1 (Simple Test Case):
 
Enter the size of the array
5
Enter array elements
9
8
7
6
5
The initial array is
[9, 8, 7, 6, 5]
The sorted array is
[5, 6, 7, 8, 9]
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
8
Enter array elements
8
7
6
9
9
6
7
8
The initial array is
[8, 7, 6, 9, 9, 6, 7, 8]
The sorted array is
[6, 6, 7, 7, 8, 8, 9, 9]

Sanfoundry Global Education & Learning Series – Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.