В чем смысл make_heap?

Если вы хотите создать приоритетную очередь из списка, вы можете использовать сделать_кучу:

Внутри куча представляет собой дерево, в котором каждый узел ссылается на значения, не превышающие его собственное значение. В кучах, созданных make_heap, конкретная позиция элемента в дереве определяется не ссылками, потребляющими память, а его абсолютным положением в последовательности, где *first всегда является самым высоким значением в куче.

Кучи позволяют добавлять или удалять элементы из нее за логарифмическое время с помощью функций push_heap и pop_heap, сохраняющих свойства кучи.

На ваш прямой вопрос хорошо ответил бы класс алгоритмов и структур данных. Кучи используются повсеместно в алгоритмах информатики. Цитируя приведенную ниже функцию make_heap, «куча — это дерево, в котором каждый узел ссылается на значения, не превышающие его собственное значение». Несмотря на то, что для кучи существует множество приложений, я использую наиболее часто проблемы поиска, когда вы хотите эффективно отслеживать отсортированный список из N значений.

У меня было такое же замешательство, как и у вас, когда я впервые столкнулся с функциями кучи STL. Хотя мой вопрос был немного о другом. Я задался вопросом: «Почему куча STL не относится к тому же классу структур данных, что и std::vector?» Я думал, что это должно работать так:

std::heap< int > my_heap;
my_heap.heap_insert( 7 );
my_heap.heap_insert( 3 );

Идея функций кучи STL заключается в том, что они позволяют создавать структуру данных кучи из нескольких различных базовых контейнеров STL, включая std::vector. Это может быть очень полезно, если вы хотите передать контейнер для использования в других местах ваших программ. Это также немного приятно, потому что вы можете выбрать базовый контейнер вашей кучи, если вы решите использовать что-то отличное от std::vector. Все, что вам действительно нужно, это следующее:

template <class RandomAccessIterator>
  void make_heap ( RandomAccessIterator first, RandomAccessIterator last );

Это означает, что вы можете создавать множество различных контейнеров в куче. Компаратор также является необязательным в сигнатуре метода, вы можете узнать больше о различных вещах, которые вы можете попробовать, на страницах STL для функции make_heap.

Ссылки:

• Структура данных кучи
• функция make_heap

Вы должны использовать std::make_heap() вместе с std::push_heap() и std::pop_heap() для поддержки двоичной кучи поверх вектора или массива; последние две функции поддерживают инвариант кучи. Вы также можете использовать std::heap_sort() для сортировки такой кучи. Хотя верно то, что вы можете использовать std::priority_queue для приоритетной очереди, это не позволит вам добраться до ее внутренностей, что, возможно, вы захотите сделать. Кроме того, std::make_heap() и std::heap_sort() вместе составляют очень простой способ выполнения пирамидальной сортировки в C++.

std::make_heap почти никогда не следует использовать на практике. Хотя кучи полезны для очередей с приоритетом, это не объясняет, почему вы хотите вручную поддерживать структуру. std::priority_queue имеет гораздо более полезный интерфейс, если все, что вам нужно, это приоритетная очередь.

Если вы используете make_heap и его братьев и сестер напрямую, вы должны обязательно использовать их каждый раз, когда вы вносите изменения в базовый контейнер. Я видел, как они использовались два или три раза, и каждый раз они использовались неправильно.

Я только один раз использовал операции с кучей напрямую, потому что мне нужно было какое-то время использовать вектор в качестве приоритетной очереди, а затем отсортировать его. Скорее всего, вам никогда не понадобится std::make_heap.

Если вам нужна приоритетная очередь с возможностью смены элементов, вы можете использовать std::set. Вы можете получить наименьший или наибольший элемент с помощью *s.begin() или *s.rbegin() соответственно и обновить элемент, удалив старое значение и вставив новое.

По сути, есть два способа построить [бинарную] кучу: создать пустую кучу и вставить в нее каждый элемент по одному или взять диапазон значений и объединить их в кучу.

Каждая операция push в куче занимает O (logn) времени, поэтому, если вы помещаете N элементов в кучу, это займет O (NlogN) времени. Однако для создания двоичной кучи из массива значений требуется всего O (N) времени.

Таким образом, имеет больше смысла вставлять каждый элемент в массив (или другой контейнер, который поддерживает итераторы произвольного доступа), а затем вызывать make_heap() для массива, чем для сохранения структуры кучи при вставке.

В дополнение к вышесказанному алгоритм сортировки STL представляет собой introsort, представляющий собой смесь быстрой сортировки и heapsort (он переключается с быстрой сортировки на heapsort, если первая работает плохо). make_heap создает структуру кучи, необходимую для запуска пирамидальной сортировки, необходимой для начальной сортировки.

Они используются для построения и поддержки структуры данных кучи.