Top K Elements

This is a great example of using a min-heap (PriorityQueue) with a HashMap to solve the “Top K Frequent Elements” problem — a popular interview question.
Let’s make it memorable by breaking it down into a story and then walking line by line.

---

🧠 The Concept Story — “Finding the Noisy Guests”

Imagine you’re throwing a party 🥳, and guests keep talking (numbers appear multiple times).
You want to find the top K noisiest guests — i.e., the ones who talk the most (appear most frequently).

You have two helpers:

1. The Secretary (HashMap) — keeps count of how many times each guest talks.
2. The Gatekeeper (PriorityQueue / Min-Heap) — only allows the top K noisiest guests inside the “VIP room”.

---

🧩 Code Walkthrough (in human language)

Step 1: Count how often each number appears

Map<Integer, Integer> numFrequencyMap = new HashMap<>();
for (int n : arr)
    numFrequencyMap.put(n, numFrequencyMap.getOrDefault(n, 0) + 1);

• Think of numFrequencyMap as a guestbook — each number (guest) gets a frequency count.
• getOrDefault(n, 0) returns 0 if the guest hasn’t spoken yet, then adds one more.

Example:
For arr = [1,3,5,12,11,12,11,12,5],
you get → {1=1, 3=1, 5=2, 12=3, 11=2}

---

Step 2: Create a min-heap based on frequency

PriorityQueue<Map.Entry<Integer, Integer>> topKElements =
        new PriorityQueue<>((e1, e2) -> e1.getValue() - e2.getValue());

• The PriorityQueue is a min-heap because the smallest frequency sits on top.
• When size ( > k ), pop the smallest (least noisy guest).

---

Step 3: Keep the top K frequent guests only

for (Map.Entry<Integer, Integer> entry : numFrequencyMap.entrySet()) {
    topKElements.add(entry);
    if (topKElements.size() > k)
        topKElements.poll();  // kick out the quietest guest
}

• We add each guest with their frequency.
• If the VIP room gets too crowded (size > K), the least noisy gets removed.

In short: “Only top K loudest guests stay!”

---

Step 4: Extract results and sort them neatly

List<Integer> topNumbers = new ArrayList<>(k);
while (!topKElements.isEmpty())
    topNumbers.add(topKElements.poll().getKey());

Collections.sort(topNumbers); // optional: just for nice increasing order
return topNumbers;

• We pull everyone from the heap (from smallest freq among top K to largest)
• Sorting is just to make final output ordered and readable.

---

🎯 Example Memory Trick

Think of it as:

“Count 🧾, Heap 🪣, Keep top K 🔝, Return 🎁.”

Those are the 4 key verbs:
Count → Heap → Trim → Return

---

⏱️ Time Complexity

• Counting: (O(n))
• Maintaining heap of size (k): (O(n \log k))
• Total ≈ (O(n \log k)) — efficient for large arrays.

---

📘 Quick Example

For input [1, 3, 5, 12, 11, 12, 11, 12, 5] and k = 3
Frequencies → {1=1, 3=1, 5=2, 11=2, 12=3}
Heap finally keeps [5,11,12] → Output [5,11,12]

---

Code

// --run-- java $tmpFile.java
import java.util.*;

public class FrequentElements{
    
    public static List<Integer> topKFrequent(int[] arr, int k) {
        List<Integer> topElements = new ArrayList<>();
        Map<Integer, Integer> frequentElements = new HashMap<>();
        PriorityQueue<Map.Entry<Integer, Integer>> topKElements = new PriorityQueue<>((e1, e2) -> e1.getValue() - e2.getValue());
        for(int num: arr) {
          frequentElements.put(num, frequentElements.getOrDefault(num, 0) + 1);
        }
        
        for(Map.Entry<Integer, Integer> element : frequentElements.entrySet()) {
            topKElements.add(element);
            if(topKElements.size()>k) {
                topKElements.poll();
            }
        }
        while(!topKElements.isEmpty()) {
            topElements.add(topKElements.poll().getKey());
        }
            Collections.reverse(topElements);
        
        return topElements;
    }
    public static void main(String [] args) {
      int [][] arrs = {{13,-21,22,22,-11,22,17,-18,24,19,-18}
      ,{1, 3, 5, 12, 11, 12, 11, 12, 5}
      };
      for(int [] arr: arrs) {
      List <Integer> topElements = topKFrequent(arr, 3);
      System.out.println("TOP Elements "+ topElements);
      }

    }
}

// --run-- java $tmpFile.java
import java.util.*;
class HelloWorld {
    public static void main(String[] args) {
        Integer [] arr = {13,-21,12,22,-11,29,17,-16,24,19,-18};
        // Arrays.sort(arr);
        List<Integer> arrys = Arrays.asList(arr);
        Collections.sort(arrys);
        Collections.reverse(arrys);
        System.out.println("Hello, World!" + arrys.get(9-1));
    }
}