Frequency Sort Using Priority Queue

When working with data structures and algorithms (DSA), one of the tasks you might encounter is frequency sorting—organizing elements based on how often they appear in a dataset. This problem can be efficiently solved using a priority queue (also known as a heap), which allows for dynamic ordering of elements.

Understanding Frequency Sort

Frequency sort involves reordering the elements of an array based on their frequency in descending order. For instance, consider the following array:

[3, 1, 2, 2, 4, 3, 3, 1]

In this array, the element 3 appears three times, 2 appears two times, and 1 appears twice as well. A frequency sorted output for this array would be:

[3, 3, 3, 2, 2, 1, 1, 4]

Elements with the same frequency are sorted in their order of first appearance. In this case, 4 is ignored in frequency sort since it only appears once and isn't relevant to the higher-frequency grouping.

Priority Queue Basics

A priority queue is a data structure that provides a way to manage a set of elements efficiently, ordering them based on their "priority." In the context of frequency sort, the priority is defined by how often each element occurs. Java has a built-in PriorityQueue class which we can utilize to achieve our goal seamlessly.

Step-by-Step Approach

Let’s break down the approach to implement frequency sort using a priority queue:

1. Count Frequencies: Use a hashmap (or a similar structure) to count how many times each element appears in the array.

2. Store in a Priority Queue: Insert these frequency counts into a priority queue. We can structure our queue to prioritize higher frequencies.

3. Build the Result: Finally, we extract elements from the priority queue and populate the result list based on their frequencies.

Java Implementation

Here’s a clear example to illustrate the entire process:

import java.util.*;

public class FrequencySort {
    public static List<Integer> frequencySort(int[] nums) {
        // Step 1: Count frequencies
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Create a priority queue to sort by frequency
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
            (a, b) -> b.getValue().compareTo(a.getValue())
        );

        // Add all entries from frequency map to the priority queue
        pq.addAll(frequencyMap.entrySet());

        // Step 3: Build result based on frequency
        List<Integer> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            Map.Entry<Integer, Integer> entry = pq.poll();
            int num = entry.getKey();
            int freq = entry.getValue();
            for (int i = 0; i < freq; i++) {
                result.add(num); // Add 'num' freq number of times
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 2, 2, 4, 3, 3, 1};
        List<Integer> sortedList = frequencySort(nums);
        System.out.println(sortedList);
    }
}

Explanation of the Code

• Counting Frequencies: We utilize a HashMap to store elements and their corresponding frequencies. The getOrDefault method assists in simplifying the counting process.

• Constructing the Priority Queue: We create a priority queue where we define our custom comparator. The comparator orders the queue based on the value of the frequency in descending order.

• Building the Result: By using a while loop, we poll the highest frequency element from the priority queue and add it to our result list the number of times it appears.

Example Output

When the above code is executed, it processes the input array and outputs:

[3, 3, 3, 2, 2, 1, 1, 4]

Complexities

• Time Complexity: The overall time complexity for this approach is O(n log n) due to the operations in the priority queue. Counting frequencies takes O(n) and adding elements to the queue takes O(log k) for each of the k distinct elements.

• Space Complexity: The space complexity is O(n) for storing the frequency map and the priority queue.

The combination of frequency counting and heap-based sorting makes this method efficient and optimal for handling frequency-based sorting. It’s not just a practical solution, but understanding it strengthens your grasp on key data structures, which is vital for interviews and real-world applications.