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.

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.

```
 
```

//Java Program to Implement Heap Sort Using a Priority Queue

```
 
```
```
import java.io.BufferedReader;
```
```
import java.io.IOException;
```
```
import java.io.InputStreamReader;
```
```
import java.util.Arrays;
```
```
 
```
```
class PriorityQueue{
```
```
    int[] arr;
```
```
    int size;
```
```
    int count;
```
```
    PriorityQueue(int size){
```
```
        this.size = size;
```
```
        arr = new int[size];
```
```
        count = 0;
```
```
    }
```

    // Function to insert an element into the priority queue

```
    void insert(int value){
```
```
        if(count == size){
```

            System.out.println("Cannot insert the key");

```
            return;
```
```
        }
```
```
        arr[count++] = value;
```
```
        heapifyUpwards(count);
```
```
    }
```

    // Function to heapify an element upwards

```
    void heapifyUpwards(int x){
```
```
        if(x<=0)
```
```
            return;
```
```
        int par = (x-1)/2;
```
```
        int temp;
```
```
        if(arr[x-1] < arr[par]){
```
```
            temp = arr[par];
```
```
            arr[par] = arr[x-1];
```
```
            arr[x-1] = temp;
```
```
            heapifyUpwards(par+1);
```
```
        }
```
```
    }
```

    // Function to extract the minimum value from the priority queue

```
    int extractMin(){
```
```
       int rvalue = arr[0];
```
```
       arr[0] = Integer.MAX_VALUE;
```
```
       heapifyDownwards(0);
```
```
       return rvalue;
```
```
    }
```

    // Function to heapify an element downwards

```
    void heapifyDownwards(int index){
```
```
        if(index >=arr.length)
```
```
            return;
```
```
        int temp;
```
```
        int min = index;
```
```
        int left,right;
```
```
        left = 2*index;
```
```
        right = left+1;
```

        if(left<arr.length && arr[index] > arr[left]){

```
            min =left;
```
```
        }
```

        if(right <arr.length && arr[min] > arr[right]){

```
            min = right;
```
```
        }
```
```
        if(min!=index) {
```
```
            temp = arr[min];
```
```
            arr[min] = arr[index];
```
```
            arr[index] = temp;
```
```
            heapifyDownwards(min);
```
```
        }
```
```
    }
```

    // Function to implement the heapsort using priority queue

```
    static void heapSort(int[] array){
```

        PriorityQueue object = new PriorityQueue(array.length);

```
        int i;
```
```
        for(i=0; i<array.length; i++){
```
```
            object.insert(array[i]);
```
```
        }
```
```
        for(i=0; i<array.length; i++){
```

            array[i] = object.extractMin();

```
        }
```
```
    }
```
```
}
```
```
public class PriorityQueueTest {
```
```
    // Function to read user input
```

    public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

```
        int n;
```

        System.out.println("Enter the number of elements in the array");

```
        try{
```

            n = Integer.parseInt(br.readLine());

```
        }catch (IOException e){
```

            System.out.println("An error occurred");

```
            return;
```
```
        }
```

        System.out.println("Enter array elements");

```
        int[] array = new int[n];
```
```
        int i;
```
```
        for(i=0; i<array.length; i++){
```
```
            try{
```

                array[i] = Integer.parseInt(br.readLine());

```
            }catch (IOException e){
```

                System.out.println("An error occurred");

```
            }
```
```
        }
```

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

        System.out.println(Arrays.toString(array));

```
        PriorityQueue.heapSort(array);
```

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

        System.out.println(Arrays.toString(array));

```
    }
```
```
}
```

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.

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.

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

« Prev - Java Program to Implement Min Hash

Related Posts:

Check Programming Books
Practice Design & Analysis of Algorithms MCQ
Check Computer Science Books
Practice Computer Science MCQs
Apply for Computer Science Internship

Recommended Articles: