What are the differences between heap and red-black tree?

Question

We know that heaps and red-black tree both have these properties:

1. worst-case cost for searching is lgN;
2. worst-case cost for insertion is lgN.

So, since the implementation and operation of red-black trees is difficult, why don't we just use heaps instead of red-black trees? I am confused.

Answer 1

You can't find an arbitrary element in a heap in O(log n). It takes O(n) to do this. You can find the first element (the smallest, say) in a heap in O(1) and extract it in O(log n). Red-black trees and heaps have quite different uses, internal orderings, and implementations: see below for more details.

Typical use

Red-black tree: storing dictionary where as well as lookup you want elements sorted by key, so that you can for example iterate through them in order. Insert and lookup are O(log n).

Heap: priority queue (and heap sort). Extraction of minimum and insertion are O(log n).

Consistency constraints imposed by structure

Red-black tree: total ordering: left child < parent < right child.

Heap: dominance: parent < children only.

(note that you can substitute a more general ordering than <)

Implementation / Memory overhead

Red-black tree: pointers used to represent structure of tree, so overhead per element. Typically uses a number of nodes allocated on free store (e.g. using new in C++), nodes point to other nodes. Kept balanced to ensure logarithmic lookup / insertion.

Heap: structure is implicit: root is at position 0, children of root at 1 and 2, etc, so no overhead per element. Typically just stored in a single array.