Time limit exceeded in Heap

Question

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 <iostream>
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 <= n && a[l] > a[i])
 largest = l;
 else
 largest = i;
 if (r <= n && a[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] < x){
 a[i] = a[i / 2];
 i /= 2;
 }
 a[i] = x;
 // cout << i << endl;
}
void Extract_Max(long long int *a, int *n){
 long long int z = a[1];
 a[1] = a[*n];
 (*n)--;
 sift_down(a, j = 1, *n);
 cout << z << endl;
}
int main(){
 int n = 0;
 int k = 0;
 int l = 0; //len
 int command = 0;
 cin >> k;
 long long int *a = new long long int[k + 1]; // n <= k
 for (int i = 0; i < k; i++){
 cin >> 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;
}

• Jamal: It may be tough for others to read your code since you use many one-letter variable names. I'm also not sure why you're using a global variable.
• Andris: Shouldn't you do a sift_up after you have inserted an item at the end of the heap in your main? sift_up is never used.
• Andris: Also you don't need to sift_down n-1 times before Extract_Max. The one sift_down in Extract_Max should be sufficient to reorder the heap after deleting the root.
• Andris: The global j is not necessary. It is set once in Extract_Max but never read. You can replace in Extract_Max sift_down(a, j = 1, *n); with sift_down(a, 1, *n);
• Bobby: I've rolled back the code to the non-working version. If you can answer your question your own, please to so by providing an appropriate answer.

Answer 1

I believe you are not using the sift_up and sift_down properly. As you can see from this Wikipedia article sift_up should be used after an insertion and sift_down after a deletion in order to reorganize the heap. Both only once.

In your code you have omitted to use sift_up after your insertion, instead you used n-1 sift_down's which have lead incidentally to the same result as one sift_up but with a much higher processing time.

So your main should look like this:

int main(){
 int n = 0;
 int k = 0;
 int l = 0; //len
 int command = 0;
 cin >> k;
 long long int *a = new long long int[k + 1]; // n <= k
 for (int i = 0; i < k; i++){
 cin >> command;
 if (command == 0){
 cin >> a[++n];
 sift_up(a, n);
 }
 else {
 Extract_Max(a, &n);
 }
 }
 delete []a;
 return 0;
}

Answer 2

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.

• Matt: C/C++ doesn't have any particular convention for function names. Win32, for instance, is written with CapitalCasing but is entirely in C, whereas the standard libraries is mostly loweralltheway (e.g. atexit) but with a light sprinkling of lower_with_underscores (e.g. va_list).
• Bobby: @Matt: Oh, wasn't sure about that.

Answer 3

First off, you're probably better off using what the standard library provides, when appropriate. For example use a priority_queue or at least push_heap, pop_heap, etc. on a vector, so there's almost nothing you have to build.

If you do build your own (to learn, or to satisfy certain rules), here's some things I would change about your existing code.

• As other people mentioned, better variable names and/or comments are a big help. But especially avoid naming a variable l (or for that matter I). Not only does it not convey anything, but it's too hard to tell apart from 1 in many fonts. As examples, in sift_down I would consider changing l to left_child, r to right_child, a to heap and n to heap_length.

• You can remove the else branch of this code; it will never change the value of largest.

  int largest = i;
  if (l <= n && a[l] > a[i])
   largest = l;
  else
   largest = i;
  

• You can avoid a local temporary by using std::swap(a[i], a[largest]); in place of the following:

  long long int x = a[i];
  a[i] = a[largest];
  a[largest] = x;
  

• If you're looking for performance, recursion is probably not the best way to get it in C++. You may be better off writing a loop that exits once it can no longer search deeper in the heap. (Note that this is likely to be a micro-optimization, and you're probably looking for an algorithmic problem.)
• With either a recursive or iterative sift_down, you're likely to want to return the final location. If you keep the recursion I would expect largest = sift_down(a, largest, n) to provide this. But since the return value isn't used, and there are no comments, it's unclear what the return value should report, or if it should be void.

Finally as an overall comment, I don't think you're approaching the problem the way it's intended to be approached. You should probably maintain a valid heap at all times (or at least after the first extract command), and each extract should probably remove the number it extracts. Your implementation might remove the extracted number, but it also appears to rebuild a heap whenever the extract is requested. Doing so throws away the algorithmic advantages of using a heap.