Question

How would the Java Program look like if I wanted to place the following values in the oder that they would be in after being bulk insterted into a heap for Heap sort and how would the heap look like after three deleteMin() commands? These would be some example values: 9 5 8 2 4 3 1 7 6 0. ( place values that were removed using a delete min at the start in order that they were removed/

Answer 1

Answer:

import java.io.*;

class GFG {

     

    // To heapify a subtree rooted with node i which is

    // an index in arr[]. n is size of heap

    static void heapify(int arr[], int n, int i)

    {

        int smallest = i; // Initialize smalles as root

        int l = 2 * i + 1; // left = 2*i + 1

        int r = 2 * i + 2; // right = 2*i + 2

        // If left child is smaller than root

        if (l < n && arr[l] < arr[smallest])

            smallest = l;

        // If right child is smaller than smallest so far

        if (r < n && arr[r] < arr[smallest])

            smallest = r;

        // If smallest is not root

        if (smallest != i) {

            int temp = arr[i];

            arr[i] = arr[smallest];

            arr[smallest] = temp;

            // Recursively heapify the affected sub-tree

            heapify(arr, n, smallest);

        }

    }

    // main function to do heap sort

    static void heapSort(int arr[], int n)

    {

        // Build heap (rearrange array)

        for (int i = n / 2 - 1; i >= 0; i--)

            heapify(arr, n, i);

        // One by one extract an element from heap

        for (int i = n - 1; i >= 0; i--) {

             

            // Move current root to end

            int temp = arr[0];

            arr[0] = arr[i];

            arr[i] = temp;

            // call max heapify on the reduced heap

            heapify(arr, i, 0);

        }

    }

    /* A utility function to print array of size n */

    static void printArray(int arr[], int n)

    {

        for (int i = 0; i < n; ++i)

            System.out.print(arr[i] + " ");

        System.out.println();

    }

    // Driver program

    public static void main(String[] args)

    {

        int arr[] = { 4, 6, 3, 2, 9 };

        int n = arr.length;

        heapSort(arr, n);

        System.out.println("Sorted array is ");

        printArray(arr, n);

    }

}

Hope I answered the questions.

If you have any doubts/queries, feel free to ask by commenting down below. I will respond within 24 hours

And if you like my answer, then please do upvote for it, your feedback really matters alot to me.

STAY HOME STAY SAFE