Don R Walsh

Exercise 6.2-1

Using Figure 6.2 as a model, illustrate the operation of MAX-HEAPIFY(A, 3) on the array \(A = \{27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0\}\).

a.) 6.2-1 Heap a

b.) 6.2-1 Heap b

c.) 6.2-1 Heap c

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] {27}
  child {node [label=above:2] {17}
        child {node [label=above:4] {16}
              child {node [label=above:8] {5}}
              child {node [label=above:9] {7}}}
        child {node [label=above:5] {13}
              child {node [label=above:10] {12}}
              child {node [label=above:11] {4}}}
        }
  child {node [label=above:3, shade] {3}
        child {node [label=above:6] {10}
              child {node [label=above:12] {8}}
              child {node [label=above:13] {9}}}
        child {node [label=above:7] {1}
              child {node [label=above:14] {0}}
              child {edge from parent[draw = none]}}
        };
\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] {27}
  child {node [label=above:2] {17}
        child {node [label=above:4] {16}
              child {node [label=above:8] {5}}
              child {node [label=above:9] {7}}}
        child {node [label=above:5] {13}
              child {node [label=above:10] {12}}
              child {node [label=above:11] {4}}}
        }
  child {node [label=above:3] {10}
        child {node [label=above:6, shade] {3}
              child {node [label=above:12] {8}}
              child {node [label=above:13] {9}}}
        child {node [label=above:7] {1}
              child {node [label=above:14] {0}}
              child {edge from parent[draw = none]}}
        };
\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] {27}
  child {node [label=above:2] {17}
        child {node [label=above:4] {16}
              child {node [label=above:8] {5}}
              child {node [label=above:9] {7}}}
        child {node [label=above:5] {13}
              child {node [label=above:10] {12}}
              child {node [label=above:11] {4}}}
        }
  child {node [label=above:3] {10}
        child {node [label=above:6] {9}
              child {node [label=above:12] {8}}
              child {node [label=above:13, shade] {3}}}
        child {node [label=above:7] {1}
              child {node [label=above:14] {0}}
              child {edge from parent[draw = none]}}
        };
\end{tikzpicture}
\end{document}