Exercise 6.3-1

Using Figure 6.3 as a model, illustrate the operation of BUILD-MAX-HEAP on the array $A = \{5, 3, 17, 10, 84, 19, 6, 22, 9 \}$.

a.) $6.3-1 Heap a$

b.) $6.3-1 Heap b$

c.) $6.3-1 Heap c$

d.) $6.3-1 Heap d$

e.) $6.3-1 Heap e$

The following LaTeX code was used to generate heap a:

\documentclass[border = 5pt, tikz]{standalone}

\begin{document}
\begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  shade/.style = {fill=black!15},
  level/.style = {sibling distance = 50mm/#1}
  ]
  \node [label=above:1] {5}
  child {node [label=above:2] {3}
        child {node [label=above:4, label=west:i, shade] {10}
              child {node [label=above:8] {22}}
              child {node [label=above:9] {9}}}
        child {node [label=above:5] {84}}}
  child {node [label=above:3] {17}
        child {node [label=above:6] {19}}
        child {node [label=above:7] {6}}};
\end{tikzpicture}
\end{document}

The following LaTeX code was used to generate heap b:

\documentclass[border = 5pt, tikz]{standalone}

\begin{document}
\begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  shade/.style = {fill=black!15},
  level/.style = {sibling distance = 50mm/#1}
  ]
  \node [label=above:1] {5}
  child {node [label=above:2] {3}
        child {node [label=above:4] {22}
              child {node [label=above:8] {10}}
              child {node [label=above:9] {9}}}
        child {node [label=above:5] {84}}}
  child {node [label=above:3, label=west:i, shade] {17}
        child {node [label=above:6] {19}}
        child {node [label=above:7] {6}}};
\end{tikzpicture}
\end{document}

The following LaTeX code was used to generate heap c:

\documentclass[border = 5pt, tikz]{standalone}

\begin{document}
\begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  shade/.style = {fill=black!15},
  level/.style = {sibling distance = 50mm/#1}
  ]
  \node [label=above:1] {5}
  child {node [label=above:2, label=west:i, shade] {3}
        child {node [label=above:4] {22}
              child {node [label=above:8] {10}}
              child {node [label=above:9] {9}}}
        child {node [label=above:5] {84}}}
  child {node [label=above:3] {19}
        child {node [label=above:6] {17}}
        child {node [label=above:7] {6}}};
\end{tikzpicture}
\end{document}

The following LaTeX code was used to generate heap d:

\documentclass[border = 5pt, tikz]{standalone}

\begin{document}
\begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  shade/.style = {fill=black!15},
  level/.style = {sibling distance = 50mm/#1}
  ]
  \node [label=above:1, label=west:i, shade] {5}
  child {node [label=above:2] {84}
        child {node [label=above:4] {22}
              child {node [label=above:8] {10}}
              child {node [label=above:9] {9}}}
        child {node [label=above:5] {3}}}
  child {node [label=above:3] {19}
        child {node [label=above:6] {17}}
        child {node [label=above:7] {6}}};
\end{tikzpicture}
\end{document}

The following LaTeX code was used to generate heap e:

\documentclass[border = 5pt, tikz]{standalone}

\begin{document}
\begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  shade/.style = {fill=black!15},
  level/.style = {sibling distance = 50mm/#1}
  ]
  \node [label=above:1] {84}
  child {node [label=above:2] {22}
        child {node [label=above:4] {10}
              child {node [label=above:8] {5}}
              child {node [label=above:9] {9}}}
        child {node [label=above:5] {3}}}
  child {node [label=above:3] {19}
        child {node [label=above:6] {17}}
        child {node [label=above:7] {6}}};
\end{tikzpicture}
\end{document}