In the solution we developed to last week's homework, we have a performance problem, which is that insert needs to know the rank of every node in the tree, but calculating those ranks takes time proportional to the number of nodes, O(n) time.
But a proper implementation of a Heap should be able to perform an insertion or deletion in time proportional to the height of the heap, which for a well-balanced tree is only O(log n) time.