I'll trace "aaabbc". Frequencies: a:3, b:2, c:1. Heap: [(a,3), (b,2), (c,1)]. Previous: none.
Step : pop (a,3), place 'a', result = "a". Previous = (a,2). Step : pop (b,2), push back (a,2), place 'b', result = "ab". Step : pop (a,2), push back (b,1), place 'a', result = "aba".
Continuing: steps through pop b, a, and c in turn, producing "ababac". No adjacent characters match.
The heap holds at most entries. Each of characters does one push and one pop at each, giving time. You store the frequency map and result string, so space is .