Какой смысл make_heap?

Question

Может кто-нибудь сказать, пожалуйста, суть шаблонов функций кучи STL, таких как std::make_heap? Зачем кому-то их использовать? Есть ли практическое применение?

Answer 1

На ваш прямой вопрос ответит класс по алгоритмам и структурам данных. Кучи повсеместно используются в алгоритмах информатики. Процитируем из функции 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

Answer 2

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

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

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

Answer 3

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

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

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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