Question: do heaps have to be balanced?
Answer: You actually don't have to keep the heap balanced. ... All you have to do is bubble up a new value on insert to a heap, or bubble down the old last element of a heap when you extract an element. Both of these are in log(n) time, which is speedy enough for most all algorithms.