4.4. Heaps¶
4.4.1. Binary Tree Space Overhead (1)¶
From the Full Binary Tree Theorem:
Half of the pointers are null.
If leaves store only data, then overhead depends on whether this is full tree.
Ex: Full tree, all nodes the same, with two pointers to children and one to element
Total space required is \((3p + d)n\)
Overhead: \(3pn\)
If \(p = d\), this means \(3p/(3p + d) = 3/4\) overhead.
4.4.2. Binary Tree Space Overhead (2)¶
Eliminate pointers from the leaf nodes
\[\frac{n/2(2p)}{n/2(2p) + dn} = \frac{p}{p + d}\]
This is 1/2 if \(p = d\).
\((2p)/(2p + d)\) if data only at leaves \(\Rightarrow\) 2/3 overhead.
Note that some method is needed to distinguish leaves from internal nodes.
4.4.3. Complete Trees¶
\[\begin{split}\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\textrm{Position} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\
\hline
\hline
\textrm{Parent} & \,--\, & 0 & 0 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5\\
\hline
\textrm{Left Child} & 1 & 3 & 5 & 7 & 9 & 11 & \,--\, & \,--\, & \,--\, &
\,--\, & \,--\, & \,--\,\\
\hline
\textrm{Right Child} & 2 & 4 & 6 & 8 & 10 & \,--\, & \,--\, & \,--\, &
\,--\, & \,--\, & \,--\, & \,--\,\\
\hline
\textrm{Left Sibling} & \,--\, & \,--\, & 1 & \,--\, & 3 & \,--\, & 5 &
\,--\, & 7 & \,--\, & 9 & \,--\,\\
\hline
\textrm{Right Sibling} & \,--\, & 2 & \,--\, & 4 & \,--\, & 6 & \,--\, & 8 &
\,--\, & 10 & \,--\, & \,--\,\\
\hline
\end{array}\end{split}\]
