[brianpgordon]

The uses of the heap are:

1. Peek the root of the heap to find the tallest rectangle in the active set. This is a constant time operation.

2. Add a new rectangle to the active set. This is a O(log(n)) operation.

3. Remove a rectangle from the active set. This is a O(log(n)) operation if you use something like a hash table to locate the element in the heap.

Each rectangle is added once (at its left edge) and removed once (at its right edge). The root of the heap is peeked on every critical point. All together, that makes the algorithm O(n log n).

Or am I missing something?