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