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

Question

[alex4answ]

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

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

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

Я так понимаю Heap используют когда нужен быстрый доступ к самому большому/маленькому элементу (зависит от направленности кучи), но опять же, чем не подходит бинарное дерево поиска или его подвиды ?

Answer 1

[Wataru]

Везде, где можно использовать кучу, можно использовать и бинарное дерево поиска. Но, куча имеет несколько приемуществ. Грубо говоря, она работает быстрее и жрет меньше памяти.

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

Comments

[alex4answ]

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

[Wataru]

alex4answ, Потому что в очередь добавляются элементы постоянно. Если бы вам были даны все значения сразу же, то вы бы просто отсортировали их и все. Но нет, как, например, в алгоритме Дейкстры - новые элементы в очередь добавляются потом и мы их заранее не знаем. В сортированный массив вставлять новые элементы очень долго - надо сдвинуть кучу элементов, чтобы освободить место для нового. Если же вы будете сортированный список делать, то на нем не получиться делать бинпоиск и найти место для вставки уже станет долго.

[alex4answ]

wataru, понял, спасибо.
Но и в куче не выйдет бин поиск использовать, тк нет четкого правила больше-меньше по сторонам, только узел A >= B
Но в целом понял, спасибо )

[Wataru]

alex4answ,

> Но и в куче не выйдет бин поиск использовать,

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