Considere max-heaps ternários, isto é, com até 3 filhos por nó, ao invés de 2. Continuamos tendo o máximo em A[1], mas agora os filhos de A[1] serão A[2], A[3] e A[4]; os filhos de A[2] serão A[5], A[6] e A[7]; e assim por diante. Sua tarefa será programar a operação Max-Heapify. Lembrando a operação abaixo para max-heaps binários, escreva um procedimento análogo para max-heaps ternários.

	  \begin{algorithm}
	  \begin{algorithmic}
	  \PROCEDURE{Max-Heapify}{$A, i$}
	  \STATE $l \gets \textrm{Left}(i)$
	  \STATE $r \gets \textrm{Right}(i)$
	  \IF{$l \leq \textit{heap-size}[A]$ \textbf{and} $A[l] > A[i]$}
	  \STATE $largest \gets l$
	  \ELSE
	  \STATE $largest \gets i$
	  \ENDIF
	  \IF{$r \leq \textit{heap-size}[A]$ \textbf{and} $A[r] > A[largest]$}
	  \STATE $largest \gets r$
	  \ENDIF
	  \IF{$largest > i$}
	  \STATE $A[i] \leftrightarrow A[largest]$
	  \STATE \textsc{Max-Heapify}$(A, largest)$
	  \ENDIF
	  \ENDPROCEDURE
	  \end{algorithmic}
	  \end{algorithm}
	

Não esqueça de redefinir funções análogas às dos heaps binários para obter os índices dos filhos e pai de cada índice. Lembre-se que temos agora três filhos: Left, Middle e Right, além do Parent. Para ajudar, eis as funções para heaps binários:

Left(i) = \(2i\)
Right(i) = \(2i+1\)
Parent(i) = \(\lfloor i/2 \rfloor\)

Solução:

Left(i) = \(3i - 1\)
Middle(i) = \(3i\)
Right(i) = \(3i + 1\)
Parent(i) = \(\lfloor (i+1)/3 \rfloor\)

	  \begin{algorithm}
	  \begin{algorithmic}
	  \PROCEDURE{Max-Heapify}{$A, i$}
	  \STATE $l \gets \textrm{Left}(i)$
	  \STATE $m \gets \textrm{Middle}(i)$
	  \STATE $r \gets \textrm{Right}(i)$
	  \IF{$l \leq \textit{heap-size}[A]$ \textbf{and} $A[l] > A[i]$}
	  \STATE $largest \gets l$
	  \ELSE
	  \STATE $largest \gets i$
	  \ENDIF
	  \IF{$m \leq \textit{heap-size}[A]$ \textbf{and} $A[m] > A[largest]$}
	  \STATE $largest \gets m$
	  \ENDIF
	  \IF{$r \leq \textit{heap-size}[A]$ \textbf{and} $A[r] > A[largest]$}
	  \STATE $largest \gets r$
	  \ENDIF
	  \IF{$largest > i$}
	  \STATE $A[i] \leftrightarrow A[largest]$
	  \STATE \textsc{Max-Heapify}$(A, largest)$
	  \ENDIF
	  \ENDPROCEDURE
	  \end{algorithmic}
	  \end{algorithm}