$($a$)$ Draw two min heaps H$1,$ H$2$ of size $5$ and the same root, each containing two

items A$1,$ A$2$ with the same key. Suppose the remove operation is performed

simultaneously for the two heaps. H$1$ should have A$1$ removed before H$2$

removes A$2,$ despite A$1$ and A$2$ having the same key.

$($b$)$ Give an algorithm for retrieving all of the paths from the root to any leaf node

in a heap. For example, a heap with $3$ nodes, Root, LeftChild, RightChild

has $2$ paths to leaf nodes:

Root $->$ LeftChild and Root $->$ RightChild.

Do not assume an array implementation for the heap. You may assume at

any node that there is access to the left child, right child, and parent.

$($c$)$ Determine the total number of paths that would be returned in part $($b$)$ for a

heap with height h$,$ that are perfect binary trees.

$($d$)$ Prove part $($c$)$ by induction.