for user defined struct, as I understand, it's easy. Just overload the operator <. However, for int/float etc.., do I really need to overload operator < for int? Here is what I tried:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool comp(const int& a, const int& b)
{
return a<b?false:true;
}
int main ()
{
int myints[] = {10,20,30,5,15};
vector<int> v(myints,myints+5);
vector<int>::iterator it;
make_heap(v.begin(), v.end(), comp);
cout << "initial min heap : " << v.front() << endl;
for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
cout<<endl;
pop_heap (v.begin(),v.end());
v.pop_back();
for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
cout<<endl;
}
the results are:
initial min heap : 5
5 10 30 20 15
30 10 15 20
now pop_heap, push_heap won't maintain the min-heap correctly? is there any easier way to achieve this? Thanks!
Edit: sorry, I didn't check the manual carefully. yes, passing comp to pop_heap or push_heap should do the trick. However, what do you mean, I should not use an external comparator? If it's not the right way, what's the common way to achieve this?
make_heap() in C++ STL. make_heap() is used to transform a sequence into a heap. A heap is a data structure which points to highest( or lowest) element and making its access in O(1) time. Order of all the other elements depends upon particular implementation, but remains consistent throughout.
To build a min heap we:Create a new child node at the end of the heap (last level). Add the new key to that node (append it to the array). Move the child up until you reach the root node and the heap property is satisfied.
Which type of heap is implemented in STL heap? Explanation: C++ STL-heap implements max heap i.e. the front of heap contains the maximum of all the elements in a range.
Another method for making min-heap using default priority_queue: This is frequently used in Competitive Programming. We first multiply all elements with (-1). Then we create a max heap (max heap is the default for priority queue).
Use std::greater<int>()
as the comparator(to all of make_heap
, push_heap
, pop_heap
). The ()
are important - std::greater<int>
is a functor class not a function, so you need an instance of it.
The answers are good, so I just wanted to add a small example. Say you have the following array:
array<int, 10> A{5,2,8,3,4,1,9,12,0,7};
and you want to create a min heap
. The quickest way to do that is to use make_heap
algorithm. However, that creates a max heap
by default. In other words, if you call:
make_heap(A.begin(), A.end());
A
becomes a max heap
. To have a min heap
, on the other hand, you need to add a comparator but do not need to implement one. Instead call the method as follows:
make_heap(A.begin(), A.end(), greater<int>());
This call will make your array a min heap
.
PS: #include <algorithm>
is necessary to use std::make_heap
.
Same operations apply to the vector
as well.
HTH!
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With