Что делает функция push_heap в C ++?

Question

Интересно, что делает функция push_heap, которая принимает три параметра?

#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;
}

Вывод этого кода

54321
15324

Также мне интересно, как я могу реализовать эту функцию вС?Потому что я буду использовать его в алгоритме A *, который я пишу в C

Answer 1

Вы неправильно используете push_heap.

После инициализации вектора необходимо поместить его в порядке кучи:

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

Чтобы добавить дополнительные элементы в кучу, вам нужно сначала переместить каждый элемент в конец вектора, затем вызвать push_heap:

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

Наконец, чтобы удалить первый элемент в куче, вам нужно вызвать pop_heap с последующим извлечением последнего элемента из вектора:

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

Функции кучи с тремя параметрами позволяют вам указать метод сравнения для управления порядком кучи, который вы делаете правильно.

Причина ручных вызовов push_back и pop_back заключается в том, что функции кучи видят итераторы только в контейнере и не имеют доступа к самому контейнеру. Поскольку итераторов недостаточно для изменения содержимого контейнера, это должен сделать владелец контейнера (вы) вручную.

Чтобы не сталкиваться с этим самостоятельно, я бы рекомендовал использовать std::priority_queue.

Answer 2

Эта функция не превращает диапазон значений в кучу!

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

предполагает, что диапазон [first,last-1) уже является действительным heap и помещает значение в позиции last-1 в кучу, перемещая его в правильную позицию, чтобы сохранить требование кучи действительным. Он использует либо оператор < для определения порядка элементов, либо указанный пользователем компаратор.