мин куча в stl без компаратора

Question

Я только начал использовать STL и в настоящее время проходил через кучу. Я просто хотел узнать, есть ли способ реализовать минимальную кучу в c ++ / cpp без компаратора.

Я попробовал следующий код (небольшая модификация от geeksforgeeks):

#include<iostream>
#include<algorithm> // for heap 
#include<vector>
using namespace std;

int main()
{
    // initializing vector;
    vector<int> vi = { 1, 6, 7, 9, 11, 4 };

    make_heap(vi.end(), vi.begin()); // swapped the start and end points

    cout << "The minimum element of heap is : ";
    cout << vi.front() << endl;

}

Вывод: 1

Я пробовал это и с другими тестовыми примерами, и, похоже, работает нормально. Просто хотел узнать, логически это правильно или нет? Это хорошая практика?

Answer 1

Прежде всего, ваш код:

make_heap(vi.end(), vi.begin());

Это приводит к неопределенному поведению , потому что vi.end() - это итератор с окончанием конца. И.Е. оно не указывает на фактическое значение, и разыменование его будет незаконным.

Я думаю, что вы пытались сделать следующее:

make_heap(vi.rbegin(), vi.rend());

Но это не сработало бы, потому что получающаяся куча все равно была бы max_heap.

Как говорится, из обсуждения в комментариях вопрос OP на самом деле является "min heap в stl без написания компаратора ", который немного отличается и приводит к совершенно другому ответу.

STL предоставляет готовые шаблонные компараторы для обработки этих случаев. Причина заключается в том, что гораздо чище иметь меньше гибких алгоритмов. Чем ниже поверхность API, тем лучше.

Все, что вам нужно сделать, это следующее:

make_heap(vi.begin(), vi.end(), std::greater<>());