CODEWITHSUNDEEP
c++
chan chong
chan chong

Reputation: 145

implementing a max and min heap in c++

So, for making a max heap, I can do the following:

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';

I have a doubt. Like I insert in a vector using the push_back operation, is there any way I can insert in a max heap like that? Or will it always be through a vector?

Secondly, this is for making a max heap. Is there something similar for min-heap? Thanks!

Upvotes: 1

Views: 1788

Answers (1)

luk32
luk32

Reputation: 16090

Inserting an element into a heap is a two-step process. 1st you need insert an element at the back of the container representing the heap. Standard push_back will do. Then you need to you use push_heap, which basically will call upheap on the last element of range.

For a different ordering, you need to usea custom version of comparator. Default one expects it to return true when 1st element is lesser than 2nd. So you need to reverse the logic. There are few ways to do it. I used lambda with explicit operator> instead of operator<. One could use some more fancy template stuff, or make use of functional.

Full code example:

#include <iostream>
#include <algorithm>

int main() {
    std::vector<int> v {10,20,30,5,15};
    std::make_heap(v.begin(), v.end());
    v.push_back(40);
    std::push_heap(v.begin(), v.end()); // notice that now the v.end() points 
                                        // to different location than before
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n';

    auto cmp = [](int a, int b) { return a>b; }; // custom comparator via lambda
    std::make_heap(v.begin(), v.end(), cmp); // make a new heap using `cmp`
    v.push_back(3);                          // add another element
    std::push_heap(v.begin(), v.end(), cmp); // restore heap structure using `cmp`
    for (auto i : v) std::cout << i << ' ';
    return 0;
}

For the sake of the example with functional's greater:

#include <iostream>
#include <algorithm>
#include <functional>

int main() {
    std::vector<int> v {10,20,30,5,15};
    auto cmp = std::greater<int>(); // make an instance of standard `greater` comparator
    std::make_heap(v.begin(), v.end(), cmp); // make a new heap using `cmp`
    v.push_back(3);                          // add another element
    std::push_heap(v.begin(), v.end(), cmp); // restore heap structure using `cmp`
    for (auto i : v) std::cout << i << ' ';
    return 0;
}

Upvotes: 5

Related Questions