Comment by gelisam

How about adding new elements with lower keys instead of decreasing the existing elements? Then, once we count that more than half of the n elements are duplicates, we could spend O(n log n) operations cleaning up the heap by recreating it.