What is Heap Sort?

Heap sort is a sorting method that works by first constructing a binary heap from the array to be sorted, then removing the maximum element from the heap and inserting it at the end of the array.

Algorithm:

The basic steps of the Heap Sort algorithm are as follows:

1. Build a max heap from the input array. This can be done in O(n) time using the “heapify” algorithm.
2. Extract the maximum element from the heap and place it at the end of the array.
3. Reduce the heap size by 1.
4. Repeat steps 2-3 until the heap size is 1.

Time Complexity:

• Worst case:  O(n log(n))
• Best case: Ω(n log(n))
• Average case: Θ(n log(n))

Implementation of the algorithm in Java:

public static void sort(int[] arr) {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // Extract elements from heap one by one
        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);
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1; // Left child
        int right = 2 * i + 2; // Right child

        // If left child is larger than root
        if (left < n && arr[left] > arr[largest])
            largest = left;

        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest])
            largest = right;

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }

The sort method is the implementation of the Heap Sort algorithm, while the heapify method is used to maintain the heap property.

Problems based on Heap Sort:

• Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order. Return the sorted array.

Example:

Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.

Solution:

class Solution {
    public int[] frequencySort(int[] nums) {
       
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        int[][] arr = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            arr[i][0] = nums[i];
            arr[i][1] = freq.get(nums[i]);
        }
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[1] != b[1]) {
                    return a[1] - b[1];
                } else {
                    return b[0] - a[0];
                }
            }
        });
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[i] = arr[i][0];
        }
        return result;
  
    }
}

• We first count the frequency of each value in nums using a HashMap freq.
• We then create a 2D array arr of size n where arr[i][0] is the value at index i in nums and arr[i][1] is the frequency count of the value at index i in nums.
• We then sort the arr using Heap Sort with a custom Comparator. The Comparator compares the frequency count of the elements. If the frequency count is the same, it compares the elements themselves in decreasing order.

Note: also read about Merge Sort

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py