Treat the array as a binary tree and rearrange it into a max-heap, where every parent is at least as large as its children. The root is then the maximum: swap it to the end, shrink the heap by one, and sift the new root down to restore the heap.
- Average time
- O(n log n)
- Space
- O(1)