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

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;
}

>Solution :

You can first use a HashMap to count the frequencies of all the numbers in the given array.

Then iterate through the hashmap to create the CountedInts objects and insert those objects into the priority queue.

Leave a Reply