Why would one use a heap over a self balancing binary search tree?

Question

What are the uses of heaps? Whatever a heap can do can also be done by a self-balancing binary search tree like an AVL tree. The most common use of heap is to find the minimum (or maximum) element in O(1) time (which is always the root). This functionality can also be included while constructing the AVL tree by maintaining a pointer to the minimum(or maximum) element, and min/max queries can be answered in O(1) time.

The only benefit of heaps over AVL trees I can think of is that AVL trees use a bit more memory because of pointers. Is there any other advantage/functionality of using a heap over an AVL tree?

Answer 1

The main reason is a binary heap is actually implemented as an array, not a tree (the tree is a metaphor, the actual implementation is an array, where the children of element with index i are elements with indices 2i+1 and 2i+2). An array is extremely more efficient (in constants) than a tree, both in space and time - due to locality of reference, making the data structure much more cache efficient, which usually results in much better constants.

In addition, initializing a binary heap with n elements takes O(n) time, while doing the same for a BST takes O(nlogn) time.