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

Question

We know that heaps and red-black wood have the following properties:

• The worst search cost is lgN;
• The worst cost to insert 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 embarrassed.

Answer 1

You cannot find an arbitrary element on the heap in O(log n) . This requires O(n) . You can find the first element (the smallest, say) on the heap in O(1) and extract it in O(log n) . Red-black trees and heaps have completely different uses, internal ordering and implementation: see below for more details.

Typical use

Red-black tree: saving the dictionary, where you can also search for items sorted by key, so that you can, for example, iterate over them in order. Insert and search O(log n) .

Heap: priority queue (and heap sorting). Extract the minimum and insert O(log n) .

Structure Constraint Constraints

Red-black tree: general order: left child <parent <right child.

Heap: dominance: parent <children.

(note that you can replace a more general order than <)

Execution / memory loss

Red-black wood: pointers used to represent the structure of the tree, therefore the overhead of the element. Usually several nodes are used, distributed in free storage (for example, using new in C ++), the nodes point to other nodes. Balance is maintained to ensure a logarithmic search / insert.

Heap: the structure is implicit: the root is at position 0, children with a root at 1 and 2, etc., so there is no overhead for the element. Usually just stored in a single array.

Answer 2

Red Ebony:
A binary search tree form with a deterministic balancing strategy. This balancing ensures good performance and can always be found in O (log n) mode.

Heap:
We need to search for each item in the heap to determine if the item is inside. Even with optimizations, I find the search is still O (N). On the other hand, it is best to find min / max in the set O (1).

Answer 3

Firstly, this is not a stackoverflow question, since Wikipedia is enough for this. (Read faq before asking questions)

Secondly, your confusion is deeper, since there is no algorithm that could look in O (log n) on the heap.

Heap trees and red and black are used in completely different scenarios.

RBT is typically used to maintain a height-balanced BST to support various operations in it, limited to the order of log n. Heaps are commonly used when implementing priority queues.