В чем смысл make_heap?

Ответ 1

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

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

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

Ответ 2

Ваш прямой вопрос будет хорошо отвечать классу в алгоритмах и структурах данных. Кучи используются повсеместно в алгоритмах в информатике. Чтобы указать из функции make_heap, приведенной ниже, "куча - это дерево, где каждый node ссылается на значения, не превышающие его собственного значения". Хотя существует множество приложений для кучи, наиболее часто используемым я использую проблемы поиска, когда вы хотите эффективно отслеживать отсортированный список значений 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

Ответ 3

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

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

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

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

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

Ответ 7

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