Why is a binary heap better as an array than a tree?

Question

When creating a binary maximum heap, why is it better to implement it as an array-based rather than a tree-like structure (at the base of the tree, like in every node, also having a parent pointer to it)? In terms of runtime analysis, memory usage, performance ...

For a binary maximum heap, the execution time is:

• insert: O (lg n)
• remove min: O (lg n)
• merge: O (n)

To implement a tree

• insert: O (lg n)
• remove min: O (lg n)
• merge: O (n)

Can someone explain in detail?

Answer 1

The tree uses more time and memory. The difficulties are the same, but the constant factors are different.

Tree pointers use a lot of memory, compared to an array based on an array, where you hardly need any extra space, except that it is taken by the values ​​themselves. And manipulating these pointers takes time. Allocating and releasing nodes can take some time and space ...

In addition, there is no guarantee that tree nodes will be merged in memory. If either of the two alternatives uses a cache, this is a bunch of arrays.

Answer 2

With reference to what has already been said through the answers of others, one may wonder why we do not use arrays for BST as well. The binary heap requires it to be a complete binary tree. Therefore, the depth of leaf nodes is always h or h-1. I believe this property makes using arrays ideal for binary heaps and unsuitable for BST (since BST does not have a requirement for a complete binary tree - it can be strict / complete / complete).