Time limit exceeded in Heap

I wrote a Heap, but the judge system reports "time limit exceeded" in some tests. I use a sift_down to build, so I don't know why.

Maybe I can improve the build? Or do I have a bad sift_down?


Input:


n commands


Commands:


0 xxx, where xxx is a number to add to heap

1 - extract maximum from heap

#include 
using namespace std;
int j = 0;

int sift_down(long long int *a, int i, int n){
    int l = 2 * i;
    int r = 2 * i + 1;
    int largest = i;
    if (l  a[i])
        largest = l;
    else
        largest = i;
    if (r  a[largest])
        largest = r;
    if (largest != i){
        long long int x = a[i];
        a[i] = a[largest];
        a[largest] = x;
        sift_down(a, largest, n);
    }
    return largest;
}

void sift_up(long long int *a, int i){
    long long x = a[i];
    while (i > 1 && a[i / 2] > k;

    long long int *a = new long long int[k + 1]; // n > command;
        if (command == 0){
            cin >> a[++n];
        }
        else {
                for(int i = n - 1; i >= 1; i--)
                    sift_down(a, i, n);
                Extract_Max(a, &n);

        }
    }

    delete []a;

    return 0;
}

Some generic comments about your code, not related to your problem.

using namespace std;

There are some developers which consider importing a whole namespace (overwriting some standard functions with imported ones) as very bad practice. I'm not qualified enough to make comments on that, but it's something you should keep in mind.

You're inconsistent about your usage of letter casing.

int sift_down( ...
void Extract_Max( ...

That's one of the things you should fix first, there is no standard for C/C++ when it comes to casing, but at least be consistent within your source code. And even better, have a look at what everyone else in your environment does and copy that.

int sift_down(long long int *a, int i, int n){
    int l = 2 * i;
    int r = 2 * i + 1;

To abuse a very popular movie quote:


I find your lack of properly named variables disturbing.

There is absolutely no valid reason to use single letter variable names in production code, with the only exception of dimensions (x, y, z) and loop variables (i, j, k).

You might also notice that, normally, an integer with the name i is only used inside loops. Seeing it as a parameter to a function is...disturbing.

The lack of comments is also problematic, especially when it comes to rather complex implementations.

StackExchange Code Review Q#36947, answer score: 3