Как обращаться с кучами в C ++

Question

Я знаю, что это, вероятно, один из тех вопросов, которые «вам просто нужно попробовать», но, поскольку у меня пока нет фактических данных испытаний, я хотел бы получить некоторую информацию о вашем опыте, пока я проектирование кода.

У меня есть структура данных, которая реализует очередь приоритетов с некоторыми добавленными функциями. Обычно мне нужно добавлять кучу объектов в эту кучу за раз. Я использую алгоритмы std::make_heap(), std::push_heap() и std::pop_heap() для поддержки инвариантов кучи.

Сейчас, когда я делаю вставку, я использую std::push_heap(), чтобы добавить единственный элемент. Теперь я думаю о добавлении всех элементов за раз, используя метод std::vector::push_back() и реорганизацию кучи. Простой push_heap() в настоящее время, вероятно, не будет работать, поэтому мне придется использовать новый make_heap(). Однако make_heap() работает в (3*(last-first)), в то время как push_heap() принимает только log(last-first).

Есть ли простой способ выяснить, какой из них на самом деле быстрее в этом случае, или мне нужно подождать, пока станут доступны тестовые данные?

Answer 1

Если вы вставите k элементов в кучу размером n , make_heap() будет быстрее примерно с точки, где k⋅log ₂ (n)> 3⋅n .Это означает, что k> 3⋅n / log ₂ (n) .Вы можете вычислить это значение перед массовой вставкой, а затем решить, какой метод будет быстрее.

Обратите внимание, что это значение является лишь приблизительной оценкой, поскольку фактическая реализация функции, вероятно, не займет точно в эти времена для выполнения операций.Но это должно быть полезно, как правило, и получать достаточно хорошие результаты.

Answer 2

make_heap выполняется не более чем с 3N сравнениями (где N - размер кучи), в то время как push_heap занимает не более log N. Однако вы должны поместить каждый элемент в кучу отдельно, что означает это занимает N push_heap с, так что метод ограничен N log N сравнений.

Следовательно, make_heap асимптотически лучше, чем N push_heap с. Если куча достаточно велика, чтобы инициализация имела значение в первую очередь, она будет лучше.