CODEWITHSUNDEEP
c++stlheap
Alptugay
Alptugay

Reputation: 1686

What does the push_heap function in C++ do?

I wonder what does the push_heap function which takes three parameters do?

#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;

class HeapCompare_f
    {
        public:

            bool operator() ( int x, int y ) const
            {
                return x > y;
            }
    };
int main()
{
    vector<int> vector1(5);

    for (int i = 0; i < 5; ++i)
        vector1[i] = 5-i;

    for (int i = 0; i < 5; ++i)
        cout << vector1[i];
    cout << endl;

    push_heap(vector1.begin(), vector1.end(),HeapCompare_f());

    for (int i = 0; i < 5; ++i)
        cout << vector1[i];
    cout << endl;



  return 0;
}

The output of this code is

54321
15324

Also I wonder how can I implement that function in C ? Because I will use it in A* algorithm which I am writing in C

Upvotes: 4

Views: 9773

Answers (2)

zennehoy
zennehoy

Reputation: 6846

You are using push_heap incorrectly.

After initializing your vector, you need to put it in heap order:

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

To add further elements into the heap, you need to first push each to the back of the vector, then call push_heap:

vector1.push_back(42);
std::push_heap(vector1.begin(), vector1.end());

Finally, to remove the first element in the heap, you need to call pop_heap, followed by popping the last element from the vector:

std::pop_heap(vector1.begin(), vector1.end());
vector1.pop_back();

The three-parameter heap functions let you specify a compare method to control the heap order, which you are doing correctly.

The reason for the manual push_back and pop_back calls is that the heap functions only see iterators into a container, and do not have access to the container itself. Since iterators are not sufficient to modify the contents of a container, this must be done manually by the owner of the container (you).

To avoid having to deal with any of this yourself, I'd recommend using a std::priority_queue.

Upvotes: 13

Christian Rau
Christian Rau

Reputation: 45948

This function does not turn a range of values into a heap!

std::push_heap(first, last [, comp])

assumes that the range [first,last-1) is already a valid heap and pushes the value at position last-1 into the heap, moving it to the correct position to keep the heap-requirement valid. It uses either the < operator to determine the ordering of the elements or a user-specified comparator.

Upvotes: 8

Related Questions