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

we know heaps , red-black tree both have these properties:

1. worst-case cost searching lgn;
2. worst-case cost insertion lgn.

so, since implementation , operation of red-black trees difficult, why don't use heaps instead of red-black trees? confused.

you can't find arbitrary element in heap in o(log n). takes o(n) this. can find first element (the smallest, say) in heap in o(1) , extract in o(log n). red-black trees , heaps have quite different uses, internal orderings, , implementations: see below more details.

typical use

red-black tree: storing dictionary lookup want elements sorted key, can example iterate through them in order. insert , lookup o(log n).

heap: priority queue (and heap sort). extraction of minimum , insertion o(log n).

consistency constraints imposed structure

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

heap: dominance: parent < children only.

(note can substitute more general ordering <)

implementation / memory overhead

red-black tree: pointers used represent structure of tree, overhead per element. typically uses number of nodes allocated on free store (e.g. using new in c++), nodes point other nodes. kept balanced ensure logarithmic lookup / insertion.

heap: structure implicit: root @ position 0, children of root @ 1 , 2, etc, no overhead per element. typically stored in single array.