Java Priority Queue of Objects :: A way to check an object's member?

June 12, 2022

Suppose I have an array of integers:

[ 1,2,3,4,5,6,1,2,3,1,2... ]

I want to know the K most frequent elements. The phrase "K most frequent" immediately makes me think of a Max Heap data structure, so I’ve decided to create a custom object to both count and prioritize elements:

public class countedInts implements Comparable<countedInts>{
    public int theInt, count;
    public countedInts(int a, int b) {
        this.theInt = a;
        this.count = b;
    }
    @Override
    public int compareTo(countedInts o) {
        return this.count - o.count;
    }
}

This object is essentially two ints, paired together. Simple.

Okay: now for the main code:

public int[] topKFreq(int[] arr, int k) {

    PriorityQueue<countedInts> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    for( int i=0; i<arr.length; i++ ) {
        // If arr[i] is not tracked with a countedInts object:
            maxHeap.offer( new countedInts(arr[i], 1) );
        // But if arr[i] is already stored within a countedInts object...
            countedInts tmp = maxHeap.get( ??? );
            tmp.count++;
            maxHeap.offer( tmp );
    }
}

You see the problem. As I consider the elements in arr, I need a way to check maxHeap to see if I have an countedInts object already checking the element. I need to look at the member of the object within the PriorityQueue. Is there a way to do this? Or is there a better strategy to this problem.

FULL DISCLOSURE: Yes, this is a LeetCode problem. I always like to research a solution before I give up and look at the solution. That’s a better way to learn.

=======================================================================

[EDIT] :: A user suggested the below strategy, which worked. Posted in case it can help others…

public class countedInts implements Comparable<countedInts>{
    public int theInt, count;
    public countedInts(int a, int b) {
        this.theInt = a;
        this.count = b;
    }
    @Override
    public int compareTo(countedInts o) {
        return this.count - o.count;
    }
}


public int[] topKFrequent(int[] arr, int k) {

    // Edge cases
    if( arr == null ) {
        return null;
    }
    else if( arr.length == 0 ) {
        return arr;
    }
    
    int[] ret = new int[k];
    HashMap<Integer,Integer> myMap = new HashMap<>();
    PriorityQueue<countedInts> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    // Populate HashMap
    for( int i=0; i<arr.length; i++ ) {
        if( !myMap.containsKey(arr[i]) ) {
            myMap.put(arr[i], 1);
        }
        else {
            myMap.put(arr[i], myMap.get(arr[i])+1);
        }
    }

    // Transfer data into MaxHeap
    for( Map.Entry<Integer, Integer> glork : myMap.entrySet() ) {
        maxHeap.offer( new countedInts(glork.getKey(), glork.getValue()) );
    }

    // Pick out K-most values
    for( int i=0; i<k; i++ ) {
        countedInts tmp = maxHeap.poll();
        ret[i] = tmp.theInt;
    }

    return ret;
}