What a great challenge. This took me to some unexplored data structures and algorithms.
My solution is in Elixir, and I solved the normal mode using a functional approach the the binary heap tree, as opposed to the in-place array swaps which seems to be the most common implementation. The functional approach is a lot more heavy-weight since it stores the subtree height and subtree size for each node, but it still runs in O(log n).
I also implemented a Huffman coder, which was surprisingly easy with the priority queue in place (and after understanding the algorithm). It was great fun to see how much I could tweak compression on large files while including the Huffman tree inside the encoded result.
My priority queue has a configurable comparison function and accepts any data types, so all in all I guess I earned 5 points :)