I'm really confused about tuple comparison in python heap when I was trying the following code

def topKFrequent(nums: List[int], k: int) -> List[int]:
    count = collections.Counter(nums)
    print(count)
    heap = []
    for key, val in count.items():
        if len(heap) >= k:
            if val > heap[0][0]:
                heapq.heapreplace(heap, (val, key))
        else:
        
            heapq.heappush(heap, (val, key))
    print(heap)
    return [item[1] for item in heap]

For example, the input nums is ["the","day","is","sunny","the","the","the","sunny","is","is"] and k = 3. The heap printed in the code is

[(2, 'sunny'), (4, 'the'), (3, 'is')]

But I think (4, 'the') > (3, 'is') since 4 > 3. Please help me solving this problem, thanks.

CodePudding user response：

If this is from the same Leetcode problem, then you could try to simplify it as such: (try to use similar syntax as much as it can...)

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    if(k == len(nums)): return nums
    dc = Counter(nums)
        
    return heapq.nlargest(k, dc, key=dc.get)
       

CodePudding user response：

But I think (4, 'the') > (3, 'is') since 4 > 3.

Yes, that is true, but these are siblings in the binary heap tree, and that means their value can compare either way. Heaps are not sorted lists. From Wikipedia:

the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children

As the two nodes you have mentioned here are not eachother's children, this rule does not apply to them.

A heap guarantees that its top (first) element has the least value, but there is no guarantee that the left child of that root element (at index 1) is the second-least value. That second-least value may sit in the root's right child (at index 2).

However, a heap does guarantee that when you pop elements from it (heappop), they will come out in sorted order.