Heap and tree data structure implementation difference

De openkb
Aller à : Navigation, rechercher

Sommaire

Questions

So I see that trees are usually implemented as a list where each node is dynamically allocated and each node contains pointers to two of its children.

But a heap is almost always implemented (or so is recommended in text books) using an array. Why is that? Is there some underlying assumption about the uses of these two data strcutures? For e.g. if you are implementing a priority queue using a min heap then the number of nodes in the queue is constant and so it can be implemented using an array of fixed size. But when you are talking/teaching about a heap in general why recommend implemeting it using an array. Or to flip the question a bit why not recommend learnig about trees with an implementation using arrays?

Answers

http://en.wikipedia.org/wiki/Category:Heaps_%28data_structures%29 http://en.wikipedia.org/wiki/Category:Heaps_%28data_structures%29

A binary heap is always a complete tree, and no operation on it moves whole subtrees around or otherwise alters the topology of the tree in any nontrivial way. This is not an assumption, the first is part of the definition of a heap and the second is immediately obvious from the definition of the operations.

First, since the Ahnentafel layout requires reserving space for every internal node (and all leaf nodes except the rightmost ones), an incomplete tree implemented this way would waste space for nodes that don t exist. Conversely, for a complete tree it s the most efficient layout possible, since all space is actually used for node data, and no space is needed for pointers.

Second, moving a subtree in the array would require copying all child elements to their new positions (since the left child s index is always twice the parent s index, the former changes when the latter changes, recursively down to the leafs). When you have nodes linked via pointers, you only need to move a few pointers around regardless of how large the trees below those pointers are. Moving subtrees is a core component of many algorithms of trees, including all kinds of binary search trees. It needs to be lightning fast for those algorithms to be efficient. Binary heap operations however never need to do this so it s a non-issue.

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/25097736/heap-and-tree-data-structure-implementation-difference

Related

Outils personnels
Espaces de noms

Variantes
Actions
Navigation
Outils