Question

Java language

1. Sort any 10 keys using Min Heap.

2. Sort any 10 keys using Max Heap.

Answer 1

Below is the code in JAVA for both the parts, sorting 10 keys using min_heap and max_heap respectively. In one program only, we have written logic for both types of heap. Since, it is nowhere mentioned in the question to construct heaps from the scratch, therefore, used priority queue inbuilt function in JAVA for which the import is "import java.util.*" as it is in util package. Sample output for sorted elements using both the heaps is attached at the end. We have used "poll" function of the priority queue which works exactly like "extract_min or extract_max" in min heap and max heap respectively, which means it returns the top element and remove it from the collection(heap, or priority queue). Priority queue implementation in JAVA is basically min_heap ,so to make it max heap we can use "Collections.reverseOrder()" as ---- PriorityQueue<Integer> max_heap = new PriorityQueue<Integer>(Collections.reverseOrder()).
To print the element of heap we use peek() method which just return the root element without removing it.

import java.util.*;
public class Main
{
        public static void main(String[] args) {

        //************ starting of sorting using MIN_HEAP ***************

                PriorityQueue<Integer> min_heap = new PriorityQueue<Integer>();
                System.out.print("add elements in to min heap:\n");
        
        // prompting user to input the elements in heap.
                Scanner sc = new Scanner(System.in);
                for(int i=0; i<10; i++){
                    min_heap.add(sc.nextInt());
                }
                
                System.out.print("sorted keys in ascending order:\n");
        
        // printing the top element every time till heap is empty. 
                while(!min_heap.isEmpty()){
                    System.out.print(min_heap.peek()+" ");
                    min_heap.poll();
                }
                
        
        System.out.print("\n");
        System.out.print("\n");

        // *********** starting of sorting using MAX_HEAP ***************

        System.out.print("add elements in to max heap:\n");
        
        PriorityQueue<Integer> max_heap = new PriorityQueue<Integer>(Collections.reverseOrder());

        // prompting user to input the elements in heap.
                for(int i=0; i<10; i++){
                    max_heap.add(sc.nextInt());
                }
                
                // declaring array to hold elements to print the sequence in ascending order.
                int arr[]=new int[10];
                int i = 0;
                
                System.out.print("sorted keys in descending order:\n");

        // printing the top element every time till heap is empty.
        // also storing elements in array to print sequence in ascending order.
                while(!max_heap.isEmpty()){
                    System.out.print(max_heap.peek()+" ");
                    arr[i++] = (int)max_heap.poll();
                }
                System.out.print("\n");
                System.out.print("sorted keys in ascending order:\n");
       
        // printing elements of array which is in ascending order.
                for(int idx = 9; idx>=0; idx--){
                    System.out.print(arr[idx]+" ");
                }
        }
}

Sample Output:-