Where and why is heap used?

Question

Data Structures

Good afternoon, I can’t understand what the essence of the heap is, and where is it really used?

Why is it used in the "priority queue", because in fact it is an array of elements sorted by priority.

Why not take the standard Map, binary search trees, etc., if sorting is needed during insert / delete operations?

As I understand it, Heap is used when you need quick access to the largest / smallest element (depending on the direction of the heap), but again, why is the binary search tree or its subspecies not suitable?

Answer 1

Wherever a heap can be used, a binary search tree can also be used. But, the heap has several benefits. Roughly speaking, it works faster and eats less memory.
Details:
- The search for the minimum operation works for a constant, not for a logarithm. But this is a trifle, because most often after the search, the minimum is removed, or a new element is added, which work for the logarithm.
- This data structure is much simpler than a balanced search tree and therefore faster. Stupidly, less effort should be spent on supporting the structure. It's easier to swap 2 elements of an array than to twist a red-black tree.
- Heap requires less memory. It only needs the elements themselves in the array. All search trees require pointers to children, some additional data, like the color of the vertex.
- The pile is always perfectly balanced. Search trees, on the other hand, can usually be 2 times higher than the ideal logarithm.
- A heap can be maintained in an array. This is much more cache friendly than scattered tree nodes pointing to each other. Therefore, the heap, not only performs fewer operations, these operations themselves are faster.