You don’t need the `key` function. Comparison on tuple will be enough.
(1, 2) < (2,3)
In addition to that `remove` (from a list) might be native but still linear in implementation. Popping off heap is logn.
You can push the entire tuple into the heap, and as long the frequency is the first item, it should work fine.