Heap in cpp stl

make_heap: rearrange elements in a range such that they form a heap

 

make_heap(begin,end, comparator)

comparator is a boolean function optional

pop_heap

push_heap

if v is a vector then

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

v.front() will give you maximum [default is maxheap without comparator]

You can pass the comparator function to each operation to maintain the heap property.

get the element by v.front()

Now pop the element using

pop_heap (v.begin(),v.end()); // can also pass comparator here 
Pop element from heap and rearranges the elements in the heap range [first,last) in such a way that the part considered a heap is shortened by one: The element with the highest value is moved to (last-1).
While the element with the highest value is moved from first to (last-1) (which now is out of the heap), the other elements are reorganized in such a way that the range [first,last-1) preserves the properties of a heap.
Now to actually remove the element from the vector you can use:

v.pop_back();

So a range can be organized into a heap by calling make_heap. After that, its heap properties are preserved if elements are added and removed from it using push_heap and pop_heap, respectively.


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

 

push_heap (v.begin(),v.end());

Given a heap in the range [first,last-1), this function extends the range considered a heap to [first,last) by placing the value in (last-1) into its corresponding location within it.

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s