Binary heap data structure - Application

Question

As per my understanding,

Binary heap(data structure) is used to represent Priority queue ADT. It is a complete binary tree satisfying heap property.

Heap property - If A is a parent node of B then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the heap.

Firstly, it helps me remember term heap, if there is a reason behind terming this data structure as heap. Because, we also use the term heap memory.

Dictionary meaning of heap - an untidy collection of things piled up haphazardly.

Question,

After learning Reb-Black tree & AVL tree data structure,

Why do we think of new data structure(Binary heap)?

Does Binary Heap solve set of problems that Red-Black or AVL tree does not fit into?

Answer 1

The major difference between a binary heap and a red-black tree is the performance on certain operations.

Binary Heap

Pros

• It makes an ideal priority queue, since the min/max element (depending on your implementation) is always O(1) access time, so no need to search for it.
• It's also very fast for insertion of new values (O(1) on average, O(log(n)) worst case.

Cons

• Slow searches for random elements.

---

RB Tree

Pros

• Better searching and insertion performance.

Cons

• Slower min/max searches.
• More overhead in general.

It should be noted that RB trees can make good schedulers too, such as the Completely Fair Scheduler introduced in Linux kernel v2.6.