Java Program to Implement Heap Sort using a Priority Queue

«

This is the Java Program to Implement Heap Sort Using a Priority Queue.

Problem Description

Given an array of integers, sort the array using heap sort which uses a priority queue. A priority queue is a min-heap in which every node is smaller than its elements.

Problem Solution

Add all the elements of the array to the priority queue. Now, remove the minimum element of the array and store it in the array starting from index 0.

advertisement
Program/Source Code

Here is the source code of the Java Program to Implement Heap Sort Using a Priority Queue. 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 a Priority Queue
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.util.Arrays;
  8.  
  9. class PriorityQueue{
  10.     int[] arr;
  11.     int size;
  12.     int count;
  13.     PriorityQueue(int size){
  14.         this.size = size;
  15.         arr = new int[size];
  16.         count = 0;
  17.     }
  18.     // Function to insert an element into the priority queue
  19.     void insert(int value){
  20.         if(count == size){
  21.             System.out.println("Cannot insert the key");
  22.             return;
  23.         }
  24.         arr[count++] = value;
  25.         heapifyUpwards(count);
  26.     }
  27.     // Function to heapify an element upwards
  28.     void heapifyUpwards(int x){
  29.         if(x<=0)
  30.             return;
  31.         int par = (x-1)/2;
  32.         int temp;
  33.         if(arr[x-1] < arr[par]){
  34.             temp = arr[par];
  35.             arr[par] = arr[x-1];
  36.             arr[x-1] = temp;
  37.             heapifyUpwards(par+1);
  38.         }
  39.     }
  40.     // Function to extract the minimum value from the priority queue
  41.     int extractMin(){
  42.        int rvalue = arr[0];
  43.        arr[0] = Integer.MAX_VALUE;
  44.        heapifyDownwards(0);
  45.        return rvalue;
  46.     }
  47.     // Function to heapify an element downwards
  48.     void heapifyDownwards(int index){
  49.         if(index >=arr.length)
  50.             return;
  51.         int temp;
  52.         int min = index;
  53.         int left,right;
  54.         left = 2*index;
  55.         right = left+1;
  56.         if(left<arr.length && arr[index] > arr[left]){
  57.             min =left;
  58.         }
  59.         if(right <arr.length && arr[min] > arr[right]){
  60.             min = right;
  61.         }
  62.         if(min!=index) {
  63.             temp = arr[min];
  64.             arr[min] = arr[index];
  65.             arr[index] = temp;
  66.             heapifyDownwards(min);
  67.         }
  68.     }
  69.     // Function to implement the heapsort using priority queue
  70.     static void heapSort(int[] array){
  71.         PriorityQueue object = new PriorityQueue(array.length);
  72.         int i;
  73.         for(i=0; i<array.length; i++){
  74.             object.insert(array[i]);
  75.         }
  76.         for(i=0; i<array.length; i++){
  77.             array[i] = object.extractMin();
  78.         }
  79.     }
  80. }
  81. public class PriorityQueueTest {
  82.     // Function to read user input
  83.     public static void main(String[] args) {
  84.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  85.         int n;
  86.         System.out.println("Enter the number of elements in the array");
  87.         try{
  88.             n = Integer.parseInt(br.readLine());
  89.         }catch (IOException e){
  90.             System.out.println("An error occurred");
  91.             return;
  92.         }
  93.         System.out.println("Enter array elements");
  94.         int[] array = new int[n];
  95.         int i;
  96.         for(i=0; i<array.length; i++){
  97.             try{
  98.                 array[i] = Integer.parseInt(br.readLine());
  99.             }catch (IOException e){
  100.                 System.out.println("An error occurred");
  101.             }
  102.         }
  103.         System.out.println("The initial array is");
  104.         System.out.println(Arrays.toString(array));
  105.         PriorityQueue.heapSort(array);
  106.         System.out.println("The sorted array is");
  107.         System.out.println(Arrays.toString(array));
  108.     }
  109. }
Program Explanation

1. In class PriorityQueue, insert() function is used to add an element to the priority queue and heapifyUpwards() function is used to move a leaf node to its appropriate position.
2. The extractMin() function returns the minimum element from the priority queue.
3. The heapifyDownwards() function, moves an element at index i to its correct position in the min-heap.
4. In heapsort function, first, all the elements are added to the priority queue, then the elements are extracted one by one.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
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 number of elements in the array
10
Enter array elements
10
9
8
7
6
5
4
3
2
1
The initial array is
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
The sorted array is
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 
Case 2 (Simple Test Case - another example):
 
Enter the number of elements in the array
7
Enter array elements
24
124
4
658
43
547
43
The initial array is
[24, 124, 4, 658, 43, 547, 43]
The sorted array is
[4, 24, 43, 43, 124, 547, 658]

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

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 & technical discussions at Telegram SanfoundryClasses.