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

A heap may have better insert and merge times. It really depends on the type of heap, but typically they are far less strict than an AVL because they don't have to worry about auto balancing after each operation.

A heap merely guarantees that all nodes follow the same style of ordering across the heap. There are of course more strict heaps like a binary heap that make inserting and merging more difficult since ordering matters more, but this is not always the case.

For example, the insert and merge times for a Fibonacci heap would be O(1) vs O(log n) for the AVL.

It is also more difficult to build the full AVL when compared to a heap.

We typically use heaps when we just want quick access to the min and max items and don't care about perfect ordering of other elements. With fast insertion, we can deal with many elements quickly and always keep our attention on the most important (or least important) ones.

Answer 2

You are correct when you say that a self-balancing binary tree can do strictly more things than a heap, and that heaps use less space for pointers. Here are some additional considerations:

• The binary heap takes much less code to implement than an AVL tree. This makes coding, debugging, and modification significantly easier.

• An AVL tree uses one object container and two pointers per data item stored. The binary heap uses zero overhead per data item stored - it is all packed into one array.

Answer 3

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.