Because the ‘heapify’ operation is O(n) and we are selecting a constant number of integers (3), we can use two different heaps (a min and a max heap) to keep an O(n) running time.
- Max-heapify the list
- Pop the top 3 elements, storing the first one popped as our max int
- Min-heapify the list (after adding elements back, or operate on a copy of the list)
- Pop the top 2 elements
- Return max(min1min2max1, max1max2max3)
Note that we have 2O(n) + 5O(logn) = O(n) operations.