Heap vs Sorting

Sorting: $O(n \log n)$ to sort, then $O(1)$ to access any element by rank. Heap: $O(n)$ to build (heapify), $O(\log n)$ per extraction. Use sorting when:

• You need multiple rank queries
• You need the entire sorted order
• The data doesn't change

Use heaps when:

• You only need the top $k$ elements
• Data arrives as a stream
• You need running extrema