Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

easy way to maintain a min heap with stl?

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?

like image 351
user268451 Avatar asked Oct 06 '11 23:10

user268451


People also ask

How do you make a heap in STL?

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.

How do I create a min-heap?

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?

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.

How can we implement minimum heap using priority queue?

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).


2 Answers

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.

like image 169
Steve Jessop Avatar answered Sep 22 '22 07:09

Steve Jessop


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!

like image 45
erol yeniaras Avatar answered Sep 22 '22 07:09

erol yeniaras