If we filter from the frequency map to create an array of only duplicates, which will take O(n), can’t we build the heap using this duplicates array in O(n) time?
This will take multiple O(n) operations and space, but the overall time complexity would still be in the order of O(n + klogn) and space complexity of O(n)?