Would like clarification on the heapq.nlargest parameter 'key'

user_10322567 0
Viewed 750

The following function returns the Top k elements in an Array. It assigns a frequency to each unique element in the Array and adds the data to the numbers dictionary.

numbers:

{1: 3, 2: 2, 3: 1}

I am confused about the heapq.nlargest(k, numbers.keys(), key=numbers.get) portion; how exactly are the iterable parameter numbers.keys() and key parameter numbers.get being utilized?

I understand that heapq.nlargest() converts numbers.keys() to a Max Heap structure, but I am confused on why specifically numbers.keys() and not just numbers?

Finally, why is the key parameter numbers.get the one being used?


def topKFrequent(self, nums, k):
    numbers = {}
    for n in nums:
        if n in numbers: numbers[n] += 1
        else: numbers[n] = 1        
    return heapq.nlargest(k, numbers.keys(), key=numbers.get)

I am trying to make sense of this:

heapq.nlargest(n, iterable[, key])

Return a list with the n largest elements from the dataset defined by iterable. key, if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: key=str.lower Equivalent to: sorted(iterable, key=key, reverse=True)[:n]

heap data-structures arrays python
1 Answers

Let us decompose it:

heapq.nlargest(k, numbers.keys(), key=numbers.get)

This code will iterate over numbers.keys(), so over the keys of the dictionary numbers. They will be sorted according to the key function numbers.get which returns the value associated to each key.

That means that you will get the keys from numbers corresponding to the k largest values.

As noted by @ShadowRanger in their comment, you could also use:

heapq.nlargest(k, numbers, key=numbers.get)

since iterating over a dictionary actualy iterates over its keys.

user_35452730
Related