alex4answ
@alex4answ

Где и для чего используют кучу (heap)?

Добрый день, не могу понять, в чем суть кучи, и где ее реально используют?

Почему именно ее используют в "очередь с приоритетом", ведь по сути это массив элементов, отсортированный по приоритету.

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

Я так понимаю Heap используют когда нужен быстрый доступ к самому большому/маленькому элементу (зависит от направленности кучи), но опять же, чем не подходит бинарное дерево поиска или его подвиды ?
  • Вопрос задан
  • 166 просмотров
Решения вопроса 1
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Везде, где можно использовать кучу, можно использовать и бинарное дерево поиска. Но, куча имеет несколько приемуществ. Грубо говоря, она работает быстрее и жрет меньше памяти.

Детали:
- Операция поиска минимума работает за константу, а не за логарифм. Но это мелочь, потому что чаще всего после поиска происходит удаление минимума, или добавление нового элемента, которые работают за логарифм.
- Эта структура данных сильно проще сбалансированного дерева поиска и поэтому работает быстрее. Тупо на поддержку структуры надо тратить меньше сил. Проще поменять местами 2 элемента массива, чем крутить красно-черное дерево.
- Куча требует меньше памяти. Тут нужны только сами элементы в массиве. Всякие деревья поиска требуют указателей на детей, какие-то дополнительные данные, вроде цвета вершины.
- Куча всегда идеально сбалансирована. Деревья поиска же обычно могут быть раза в 2 выше, чем идеальный логарифм.
- Кучу можно поддерживать в массиве. Это сильно дружественнее к кэшу процессора, чем разбросанные вершины дерева с указателями друг на друга. Поэтому куча, мало того, что выполняет меньше операций, эти операции сами происходят быстрее.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы