Binary Heap Data Structure - Application

Question

As far as I understand,

A binary heap (data structure) is used to represent the APT priority queue. This is a complete binary tree satisfying the heap property.

Heap property. If A is the parent node of B, then the key (value) of node A is ordered relative to the key of node B with the same order that applies to the heap.

First of all, it helps me remember a bunch of terms if there is a reason why this data structure is called a bunch. Because we also use heap memory.

The heap's vocabulary is an untidy collection of things stacked randomly.

Question

By examining the tree structure of the tree of the rib-black tree and AVL,

Why are we thinking about a new data structure (binary heap)?

Does the binary heap break many problems that the Red-Black or AVL tree does not fit into?

Answer 1

The main difference between the binary heap and the red-black tree is the performance of certain operations.

Binary heap

Pros

• This is an ideal priority queue, since the min / max element (depending on your implementation) is always O(1)access time, so there is no need to look for it.
• It is also very fast for entering new values ​​( O(1)on average, the O(log(n))worst case.

Against

• Slow search for random items.

---

RB tree

Pros

• Improved search and insertion.

Against

• Slower min / max searches.
• .

, RB , , Linux v2.6.