Time Limit Exceeded for build_max_heap

This problem is from HackerEarth:


The Monk learned about priority queues recently and asked his teacher for an interesting problem. So his teacher came up with a simple problem. He now has an integer array A. For each index i, he wants to find the product of the largest, second largest and the third largest integer in the range [1,i].


Note: Two numbers can be the same value-wise but they should be distinct index-wise.

Input:

• The first line contains an integer N, denoting the number of elements in the array A.

• The next line contains N space separated integers, each denoting the ith integer of the array A.

Output:


Print the answer for each index in each line. If there is no second largest or third largest number in the array A upto that index, then print "-1", without the quotes.

Constraints:


1

• For the third index, the top 3 numbers are 3,2 and 1 whose product is 6.

• For the fourth index, the top 3 numbers are 4,3, and 2 whose product is 24.

• For the fifth index, the top 3 numbers are 5,4 and 3 whose product is 60.

Time Limit: 1.0 sec(s) for each input file.


Memory Limit: 256 MB


Source Limit: 1024 KB


Marking Scheme: Marks are awarded if any testcase passes.


Allowed Languages: C, CPP, CLOJURE, CSHARP, GO, HASKELL, JAVA, JAVASCRIPT, JAVASCRIPT_NODE, LISP, OBJECTIVEC, PASCAL, PERL, PHP, PYTHON, RUBY, R, RUST, SCALA

Here is my solution:

```
#include
#include

#define lld long long
int n, N = 0;
using namespace std;
void max_heapify(int arr[], int n, int i){
int largest = i;
int left = 2 * i;
int right = 2*i + 1;
if(left arr[largest]){
largest = left;
}
if(right arr[largest]){
largest = right;
}
if(largest != i){
swap(arr[i], arr[largest]);
max_heapify(arr, n, largest);
}
}
void build_max_heap(int arr[], int n){
for(int i = n/2; i >=1; i--){
max_heapify(arr,n,i);
}
}

int extract_max

First of all, it's probably best to realize that a heap isn't particularly useful for this problem as it's specified. It can be used, but it doesn't really contribute much (if anything at all).

If you do use a heap, you want to take the specific properties of a max heap into account. In particular, a heap is arranged so each node is at least as large as any of its descendant nodes. As such, the first node is always the largest. The second largest is one of the second and third. In a typical case, the other of the second and third will be the third largest (and depending on how we insert items into the heap, we can enforce that being the case, which we probably want to do here). This allows us to find the three largest items in the heap without actually removing them from the heap at all.

As to why we don't need to use a heap, and why it doesn't really contribute much: we really only care about the three largest items seen at any given point. That being the case, we can start with the first three. They're clearly the largest seen to that point, so their product is the first (meaningful) output. Then we want to find the smallest of those three. Compare that to the fourth item, and if it's larger, copy it over the smallest of the first three, then print the product of the first three. Repeat that (find smallest, check against next item, get new value if larger, print out product) until we reach the end of the input.

This requires something like four comparisons (and possibly one assignment) per iteration, regardless of the number of inputs. A quick test shows it running in ~400 ms on my machine

At least in theory, this can be further optimized by observing that the smallest of the first three can only change when we add a new (larger) item to the first three. When we read a number and it's smaller than the smallest of the first three, we can print the previous product, throw away the new number, and repeat.

At least in a quick test on my machine, the latter doesn't seem to make a noticeable difference though. This is probably because the actual computation is already fast enough to keep up with the I/O, so speeding the computation up even more makes little (or no) difference. It's also possible, however that with only three numbers to look at, it's just as fast to scan them as it is to decide whether to scan them or not.

StackExchange Code Review Q#126237, answer score: 3