Why one should use Heap where we have STL (set)?

Answer 1

Consider a sorting algorithm for both heap and stl based program with two cases:
1st Case: it take O(n) to create a heap and O(log n) or O(k*log n) time to get maximal element(for k numbers) so the total complexity for such problem is O(n+ k*log n) and for larger input (log n) will become insignificant so overall complexity become O(n).
2nd Case: when we use STL to sort any sequence it takes O(n*log n) time complexity.

So now it cleared that we should use heap not only in sorting but also there are several examples where we can efficiently use it over STL.
See, I wrote code for heap and using stl both to sort a large sequence.
1st Using heap :

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int test;
    scanf("%lld",&test);
    vector<long long int> v(test);
    for(long long int i=0;i<test;i++)
    {
        scanf("%lld",&v[i]);
    }
    make_heap(v.begin(),v.end());
    sort_heap(v.begin(),v.end());  //sort using heap
    for(long long int i=0;i<v.size();i++)
    {
        printf("%lld\n",v[i]);
    }
    return 0;
}

2nd Using STL :

#include<bits/stdc++.h>
using namespace std;

int main()
{
    long long int test;
    scanf("%lld",&test);
    long long int v[test];
    for(long long int i=0;i<test;i++)
    {
        scanf("%lld",&v[i]);
    }
    sort(v,v+test);   
    for(long long int i=0;i<test;i++)
    {
        printf("%lld\n",v[i]);
    }
    return 0;
}

Comments

Thanks @admin for selecting best ans.

Answer 2

In Heap we can store equal data in multiple time but in set only can be store unique data.

Answer 3

// heap using example

#include <iostream>     // std::cout
#include <algorithm>    // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,5,15};
  std::vector<int> v(myints,myints+5);

  std::make_heap (v.begin(),v.end());
  std::cout << "initial max heap   : " << v.front() << '\n';

  std::pop_heap (v.begin(),v.end()); v.pop_back();
  std::cout << "max heap after pop : " << v.front() << '\n';

  v.push_back(99); std::push_heap (v.begin(),v.end());
  std::cout << "max heap after push: " << v.front() << '\n';

  std::sort_heap (v.begin(),v.end());

  std::cout << "final sorted range :";
  for (unsigned i=0; i<v.size(); i++)
    std::cout << ' ' << v[i];

  std::cout << '\n';

  return 0;
}

Comments

But how this answers the original question that why one should use heap over STL?

---

Hi check my ans and let me know if still you have any doubt ?