# C++ solution using heap faster than sort!

• ``````int hIndex(vector<int>& citations) {
int len = citations.size(), last = INT_MIN;
make_heap(citations.begin(),citations.end(),greater<int>());
for (int h = len;h >0;--h) {
if (citations[0] >= h && last <= h)
return h;
last = citations[0];
pop_heap(citations.begin(),citations.end()-(len-h),greater<int>());
}
return 0;
}``````

• How much faster?

• In my test, it's 8ms vs 12ms. You may say it's still O(nlogn), but it's different from the O(nlogn) of sort. I just want to provide some new thought!

• Yeah yeah, it's definitely good, I was just wondering what you meant. I didn't even know whether you meant actual time in milliseconds (and it's nice to know how much) or the complexity class :-). Btw, I guess you could call it O((n-h) log n).

• I rewrote it so it searches in the other direction (from most cited papers to least cited papers):

``````int hIndex(vector<int>& citations) {
int len = citations.size();
make_heap(citations.begin(), citations.end());
for (int h=0; h<len; ++h) {
if (citations[0] <= h)
return h;
pop_heap(citations.begin(), citations.end()-h);
}
return len;
}
``````

That's then O(h log n) and I was hoping it would be faster than your original, both because I don't use "last" and because I think h should usually be smaller than n-h (like the picture in Wikipedia's article suggests).

Obsolete: But in the OJ, it's actually slower: 16-20ms vs your 8ms. Sadly, the OJ has rather unrealistic data. It looks random and the only really large case (more than 100 papers) is a case with 10000 papers and the citations are in the millions, so h is 10000 :-(. I need to go through all 10000 papers, you stop right at the start.

Update: After I pointed this out, the large unrealistic case was replaced with a more realistic one. Now it's 5000 papers and h is around 850. Your solution didn't get worse, it's still at 8 ms, but my version is now at 4 ms (each every time in three attempts).

• You are so conscientious! Great job!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.