Why heaps exist when we have trees

[gidireich]

Any ideas about a serious advantage of a heap over a balanced BST?

I see that heap can be implemented in an array, and the code is simpler. Fine, that's something. When only heap is needed, it'll be somewhat more efficient, but not asimptoticaly.

Does anybody see any qualitive advantage of heaps over balanced BSTs?

(If we cache the maximum in a BST we have the same O(1) getMax operation. )

Thanks

[laserlight]

Advantage over a balanced BST in what situation?

For example, suppose you intend to sort an array in place with O(n log n) worst case for a comparison based sort. That's a seriously impossible-to-beat advantage of a heap compared to a balanced BST :)

This example actually is quite realistic, e.g., introsort, a hybrid comparison based sorting algorithm that does see actual use in libraries, uses quicksort, but switches to heap sort when it detects that quicksort may hit a worst case scenario.