My professor asks this question: Binary Search tree has Rotation Method to prevent it from degenerating into a linear structure (unbalanced tree). Why is there no need for such method for Binary Heaps?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Hint: What happens when you binary heap is indeed a path? Being unbalanced does not affect the overall amortized runtime. $\endgroup$– BearAqua the LogicianCommented May 2, 2019 at 15:45
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
You must refer to the definition of a Binary Heap:
A Binary heap is by definition a complete binary tree ,that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
It is by definition that it is never unbalanced. The maximum difference in balance of the two subtrees is 1, when the last level is partially filled with nodes only in the left subtree.
answered May 2, 2019 at 10:49
$\begingroup$
$\endgroup$
The question is a little confusing, since a binary heap is usually implemented in an array, not a tree. The tree is used for visualization.
Consider the following heap:
It is given by the following array:
$H=[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]$
Since a complete binary tree corresponds to an array, the opposite also holds. New elements are added to the first available index of $H$, then bubbled up. If we had imagined the tree corresponding to $H$ after insertion of a new element $x$, $x$ would appear as the right child of element $7$ (before we correct the heap).
Note that the following holds for the binary tree above that represents the heap:
- $parent(i) = \lfloor \frac{i}{2} \rfloor $
- $i \rightarrow left = 2i $
- $i \rightarrow right= 2i+1 $
We can easily bubble elements up and down by using these indexes, so we actually don't need to implement the tree at all. The answer to your professor question would be that the array $H$ always corresponds to a complete binary tree, and if by chance $|H|=2^k-1$ it corresponds to a full binary tree.
$\begingroup$
$\endgroup$
Because new nodes are inserted from right to left in a heap unlike binary search tree. While inserting nodes in a heap if there arises distortion in heap property, the new inserted node is bubbled up according to its key in the suitable position.
