Heaps against binary trees - how to implement?

Question

when implementing the heap structure, we can store data in an array so that the children from node in position I are in position 2i and 2i + 1.

My question is: why do not we use an array to represent binary search trees, but instead deal with pointers, etc.?

thanks

Answer 1

If the position of all the children is statically pre-calculated in this way, then the array essentially represents a completely complete, completely balanced binary tree.

Not all binary trees in "real life" are completely full and perfectly balanced. If you must have several particularly long branches, you will have to make the whole array much larger to place all the nodes at the lowest level.

• If the binary tree associated with the array is mostly empty, most of the array space is lost.

• If only some branches of the tree are deep enough to reach the "bottom" of the array, there is also a lot of space lost.

• If the tree (or only one branch) should grow "deeper" than the size of the array allows, this will require the "growth" of the array, which is usually implemented as copying to a larger array. This is an expensive operation.

So: Using pointers allows us to dynamically and flexibly develop a structure. Representing a tree in an array is a good academic exercise and works well for small and simple cases, but often does not satisfy the requirements of "real" calculations.

Answer 2

Personally

• Because, using pointers, increase the size of the data structure dynamically

• I find it easier to maintain a basket tree than a bunch

• Algorithms for balancing, deleting, inserting elements into a tree will only change pointers and will not physically move then, as in a vector.

etc.

Answer 3

Mostly because the recursive tree allows very simple code. If you smooth the tree into an array, the code becomes very complicated because you need to do a lot of bookkeeping, which is a recursive algorithm for you.

In addition, a tree of height N may have something between nodes N and 2^(N+1)-1 (only actual nodes require memory. If you use an array, you should always allocate space for all nodes (even empty ones) if you are not using a sparse array (which would make the code even more complex.) Therefore, although it is easy to store a rare tree with a height of 100 in memory, it would be problematic to find a computer that can allocate 20282409603651670423947251286008 bytes of RAM.

Answer 4

To insert an item into the heap, you can put it anywhere and swap it with your parent until the heap restriction is again valid. Swap-with-parent is an operation that preserves the integrity of the binary tree structure of the heap. This means that a heap of size N will be represented as an array of N-cells, and you can add a new element at logarithmic time.

A binary search tree can be represented as an array of size N using the same presentation structure as the heap (children 2n and 2n + 1), but inserting an element in this way is much more difficult, because unlike the heap constraint, to limit the binary search tree twists are required to extract a balanced tree. Thus, either you manage to save the N node tree in an N-cell array at a price higher than the logarithmic price, or you lose space by saving the tree in a larger array (if my memory serves, the red back tree can spend up to 50% of your array).

Thus, a binary search tree in an array is interesting only if the data inside is constant. And if so, then you do not need a heap structure (children 2n and 2n + 1): you can just sort your array and use binary search .

Answer 5

As far as I know, we can use Array to represent binary search trees. But more flexible use of pointers.

Answer 6

An array-based implementation is useful if you need a bunch that is used as a priority queue in graph algorithms. In this case, the elements in the heap are constant, you type the top element and insert new elements. Removing the top element (or min-element) requires some rebalancing to become a bunch again, which can be done so that the array is reasonably balanced.

The reference to this is Goldberg and Tarjan's algorithm for efficiently computing the optimal network flow in directed graphs, iirc.