Exercise 6.4-1

Using Figure 6.4 as a model, illustrate the operation of HEAPSORT on the array $A = \{5, 13, 2, 25, 7, 17, 20, 8, 4\}$.

a.) $6.4-1 Heap a$

b.) $6.4-1 Heap b$

c.) $6.4-1 Heap c$

d.) $6.4-1 Heap d$

e.) $6.4-1 Heap e$

f.) $6.4-1 Heap f$

g.) $6.4-1 Heap g$

h.) $6.4-1 Heap h$

i.) $6.4-1 Heap i$

$A = \{2, 4, 5, 7, 8, 13, 17, 20, 25\}$.

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 {25}
  child {node {13}
        child {node {8}
              child {node {5}}
              child {node {4}}}
        child {node {7}}}
  child {node {20}
        child {node {17}}
        child {node {2}}};
\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 {20}
  child {node {13}
        child {node {8}
              child {node {5}}
              child {node [shade] {25} edge from parent[draw=none]}}
        child {node {7}}}
  child {node {17}
        child {node {4}}
        child {node {2}}};
\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 {17}
  child {node {13}
        child {node {8}
              child {node [shade] {20} edge from parent[draw=none]}
              child {node [shade] {25} edge from parent[draw=none]}}
        child {node {7}}}
  child {node {5}
        child {node {4}}
        child {node {2}}};
\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 {13}
  child {node {8}
        child {node {2}
              child {node [shade] {20} edge from parent[draw=none]}
              child {node [shade] {25} edge from parent[draw=none]}}
        child {node {7}}}
  child {node {5}
        child {node {4}}
        child {node [shade] {17} edge from parent[draw=none]}};
\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 {8}
  child {node {7}
        child {node {2}
              child {node [shade] {20} edge from parent[draw=none]}
              child {node [shade] {25} edge from parent[draw=none]}}
        child {node {4}}}
  child {node {5}
        child {node [shade] {13} edge from parent[draw=none]}
        child {node [shade] {17} edge from parent[draw=none]}};
\end{tikzpicture}
\end{document}

The following LaTeX code was used to generate heap f:

\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 {7}
  child {node {4}
        child {node {2}
              child {node [shade] {20} edge from parent[draw=none]}
              child {node [shade] {25} edge from parent[draw=none]}}
        child {node [shade] {8} edge from parent[draw=none]}}
  child {node {5}
        child {node [shade] {13} edge from parent[draw=none]}
        child {node [shade] {17} edge from parent[draw=none]}};
\end{tikzpicture}
\end{document}

The following LaTeX code was used to generate heap g:

\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 {5}
  child {node {4}
        child {node [shade] {7} edge from parent[draw=none]
              child {node [shade] {20} edge from parent[draw=none]}
              child {node [shade] {25} edge from parent[draw=none]}}
        child {node [shade] {8} edge from parent[draw=none]}}
  child {node {2}
        child {node [shade] {13} edge from parent[draw=none]}
        child {node [shade] {17} edge from parent[draw=none]}};
\end{tikzpicture}
\end{document}

The following LaTeX code was used to generate heap h:

\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 {4}
  child {node {2}
        child {node [shade] {7} edge from parent[draw=none]
              child {node [shade] {20} edge from parent[draw=none]}
              child {node [shade] {25} edge from parent[draw=none]}}
        child {node [shade] {8} edge from parent[draw=none]}}
  child {node [shade] {5} edge from parent[draw=none]
        child {node [shade] {13} edge from parent[draw=none]}
        child {node [shade] {17} edge from parent[draw=none]}};
\end{tikzpicture}
\end{document}

The following LaTeX code was used to generate heap i:

\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 {2}
  child {node [shade] {4} edge from parent[draw=none]
        child {node [shade] {7} edge from parent[draw=none]
              child {node [shade] {20} edge from parent[draw=none]}
              child {node [shade] {25} edge from parent[draw=none]}}
        child {node [shade] {8} edge from parent[draw=none]}}
  child {node [shade] {5} edge from parent[draw=none]
        child {node [shade] {13} edge from parent[draw=none]}
        child {node [shade] {17} edge from parent[draw=none]}};
\end{tikzpicture}
\end{document}