Heapsort - ime.usp.br coelho/mac5711-2004/aulas/material/aula8.pdf · Heapsort CLRS 6 (veja tb CLRS…

  • Published on
    26-Jan-2019

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<p>AULA 8</p> <p>Algoritmos p.349/434</p> <p>Heapsort</p> <p>CLRS 6</p> <p>(veja tb CLRS B.5.3)</p> <p>Merge sort ilustrou uma tcnica (ou paradigma, ou estratgia) de concepo de algoritmoseficientes: a diviso e conquista.</p> <p>Heapsort ilustra o uso de estruturas de dados no projeto de algoritmos eficientes.</p> <p>Algoritmos p.350/434</p> <p>Ordenao</p> <p>A[1 . . n] crescente se A[1] A[n].</p> <p>Problema: Rearranjar um vetor A[1 . . n] de mode que elefique crescente.</p> <p>Entra:</p> <p>1 n</p> <p>33 55 33 44 33 22 11 99 22 55 77</p> <p>Sai:</p> <p>1 n</p> <p>11 22 22 33 33 33 44 55 55 77 99</p> <p>Algoritmos p.351/434</p> <p>Ordenao</p> <p>A[1 . . n] crescente se A[1] A[n].</p> <p>Problema: Rearranjar um vetor A[1 . . n] de mode que elefique crescente.</p> <p>Entra:</p> <p>1 n</p> <p>33 55 33 44 33 22 11 99 22 55 77</p> <p>Sai:</p> <p>1 n</p> <p>11 22 22 33 33 33 44 55 55 77 99</p> <p>Algoritmos p.351/434</p> <p>Ordenao por seleom = 5</p> <p>1 max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>Algoritmos p.352/434</p> <p>Ordenao por seleom = 5</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>Algoritmos p.353/434</p> <p>Ordenao por seleom = 5</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>Algoritmos p.353/434</p> <p>Ordenao por seleom = 5</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>Algoritmos p.353/434</p> <p>Ordenao por seleom = 5</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>Algoritmos p.353/434</p> <p>Ordenao por seleom = 5</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>j max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>1 max n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>Algoritmos p.353/434</p> <p>Ordenao por seleo</p> <p>1 m n</p> <p>38 10 20 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>38 10 20 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>20 10 38 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>1 n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>Algoritmos p.354/434</p> <p>Ordenao por seleo</p> <p>1 m n</p> <p>38 10 20 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>20 10 38 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>1 n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>Algoritmos p.354/434</p> <p>Ordenao por seleo</p> <p>1 m n</p> <p>38 10 20 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>38 10 20 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>20 10 38 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>1 n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>Algoritmos p.354/434</p> <p>Ordenao por seleo</p> <p>1 m n</p> <p>38 10 20 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>20 10 38 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>1 n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>Algoritmos p.354/434</p> <p>Ordenao por seleo</p> <p>1 m n</p> <p>38 10 20 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>20 10 38 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>20 10 38 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>1 n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>Algoritmos p.354/434</p> <p>Ordenao por seleo</p> <p>1 m n</p> <p>38 10 20 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>20 10 38 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>1 n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>Algoritmos p.354/434</p> <p>Ordenao por seleo</p> <p>1 m n</p> <p>38 10 20 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>20 10 38 44 50 50 55 60 75 85 99</p> <p>1 m n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>1 n</p> <p>10 20 38 44 50 50 55 60 75 85 99</p> <p>Algoritmos p.354/434</p> <p>Ordenao por seleo</p> <p>Algoritmo rearranja A[1 . . n] em ordem crescente</p> <p>ORDENA-POR-SELEO (A, n)1 para m n decrescendo at 2 faa</p> <p>2 max m3 para j m 1 decrescendo at 1 faa4 se A[max ] &lt; A[j]5 ento max j</p> <p>6 A[m] A[max ]</p> <p>Algoritmos p.355/434</p> <p>InvariantesRelao invariante chave:</p> <p>(i0) na linha 1 vale que: A[m. . n] crescente.</p> <p>1 m n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>Supondo que a invariante vale. Correo do algoritmo evidente.</p> <p>No incio da ltima iterao das linhas 16 tem-se quem = 1. Da invariante conclui-se que A[1 . . n] crescente.</p> <p>Algoritmos p.356/434</p> <p>InvariantesRelao invariante chave:</p> <p>(i0) na linha 1 vale que: A[m. . n] crescente.</p> <p>1 m n</p> <p>38 50 20 44 10 50 55 60 75 85 99</p> <p>Supondo que a invariante vale. Correo do algoritmo evidente.</p> <p>No incio da ltima iterao das linhas 16 tem-se quem = 1. Da invariante conclui-se que A[1 . . n] crescente.</p> <p>Algoritmos p.356/434</p> <p>Mais invariantes</p> <p>Na linha 1 vale que:</p> <p>(i1) A[1 . . m] A[m+ 1];Na linha 3 vale que:</p> <p>(i2) A[j + 1 . . m] A[max ]</p> <p>1 j max m n</p> <p>38 50 20 44 10 25 55 60 75 85 99</p> <p>invariantes (i1),(i2)+ condio de parada do para da linha 3+ troca linha 6 validade (i0)</p> <p>Verifique!</p> <p>Algoritmos p.357/434</p> <p>Mais invariantes</p> <p>Na linha 1 vale que:</p> <p>(i1) A[1 . . m] A[m+ 1];Na linha 3 vale que:</p> <p>(i2) A[j + 1 . . m] A[max ]</p> <p>1 j max m n</p> <p>38 50 20 44 10 25 55 60 75 85 99</p> <p>invariantes (i1),(i2)+ condio de parada do para da linha 3+ troca linha 6 validade (i0)</p> <p>Verifique!</p> <p>Algoritmos p.357/434</p> <p>Consumo de tempo</p> <p>linha todas as execues da linha1 = (n)2 = (n)3 = (n2)4 = (n2)5 = O(n2)6 = (n)</p> <p>total = (2n2 + 3n) + O(n2) = (n2)</p> <p>Algoritmos p.358/434</p> <p>Representao de rvores em vetores</p> <p>Interferncia!puta que o pariu!!!</p> <p>PSfrag replacements</p> <p>1</p> <p>1</p> <p>2</p> <p>2</p> <p>3</p> <p>3</p> <p>4</p> <p>4</p> <p>5</p> <p>5</p> <p>6</p> <p>6</p> <p>7</p> <p>7</p> <p>8</p> <p>8</p> <p>9</p> <p>9 10</p> <p>10</p> <p>11</p> <p>11</p> <p>12</p> <p>12</p> <p>nvel</p> <p>0</p> <p>1</p> <p>2</p> <p>3</p> <p>Algoritmos p.359/434</p> <p>Pais e filhosA[1 . . m] um vetor representando uma rvore.Diremos que para qualquer ndice ou n i,</p> <p>bi/2c o pai de i;2 i o filho esquerdo de i;</p> <p>2 i+ 1 o filho direito.</p> <p>O n 1 no tem pai e chamado de raiz.</p> <p>Um n i s tem filho esquerdo se 2 i m.Um n i s tem filho direito se 2 i+ 1 m.Um n i um folha se no tem filhos, ou seja 2 i &gt; m.</p> <p>Todo n i raiz da subrvore formada por</p> <p>A[i, 2i, 2i+ 1, 4i, 4i+ 1, 4i+ 2, 4i+ 3, 8i, . . . , 8i+ 7, . . .]</p> <p>Algoritmos p.360/434</p> <p>NveisCada nvel p, exceto talvez o ltimo, tem exatamente 2p nse esses so</p> <p>2p, 2p + 1, 2p + 2, . . . , 2p+1 1.</p> <p>O n i pertence ao nvel blg ic.Prova: Se p o nvel do n i, ento</p> <p>2p i &lt; 2p+1 lg 2p lg i &lt; lg 2p+1 </p> <p>p lg i &lt; p+ 1</p> <p>Logo, p = blg ic.</p> <p>Algoritmos p.361/434</p> <p>NveisCada nvel p, exceto talvez o ltimo, tem exatamente 2p nse esses so</p> <p>2p, 2p + 1, 2p + 2, . . . , 2p+1 1.</p> <p>O n i pertence ao nvel ???.</p> <p>O n i pertence ao nvel blg ic.Prova: Se p o nvel do n i, ento</p> <p>2p i &lt; 2p+1 lg 2p lg i &lt; lg 2p+1 </p> <p>p lg i &lt; p+ 1</p> <p>Logo, p = blg ic.</p> <p>Algoritmos p.361/434</p> <p>NveisCada nvel p, exceto talvez o ltimo, tem exatamente 2p nse esses so</p> <p>2p, 2p + 1, 2p + 2, . . . , 2p+1 1.</p> <p>O n i pertence ao nvel blg ic.Prova: Se p o nvel do n i, ento</p> <p>2p i &lt; 2p+1 lg 2p lg i &lt; lg 2p+1 </p> <p>p lg i &lt; p+ 1</p> <p>Logo, p = blg ic.</p> <p>Algoritmos p.361/434</p> <p>NveisCada nvel p, exceto talvez o ltimo, tem exatamente 2p nse esses so</p> <p>2p, 2p + 1, 2p + 2, . . . , 2p+1 1.</p> <p>O n i pertence ao nvel blg ic.Prova: Se p o nvel do n i, ento</p> <p>2p i &lt; 2p+1 lg 2p lg i &lt; lg 2p+1 </p> <p>p lg i &lt; p+ 1</p> <p>Logo, p = blg ic.Portanto o nmero total de nveis ???.</p> <p>Algoritmos p.361/434</p> <p>NveisCada nvel p, exceto talvez o ltimo, tem exatamente 2p nse esses so</p> <p>2p, 2p + 1, 2p + 2, . . . , 2p+1 1.</p> <p>O n i pertence ao nvel blg ic.Prova: Se p o nvel do n i, ento</p> <p>2p i &lt; 2p+1 lg 2p lg i &lt; lg 2p+1 </p> <p>p lg i &lt; p+ 1</p> <p>Logo, p = blg ic.Portanto, o nmero total de nveis 1 + blgmc.</p> <p>Algoritmos p.361/434</p> <p>Altura</p> <p>A altura de um n i o maior comprimento de um caminhode i a uma folha.</p> <p>Em outras palavras, a altura de um n i o maiorcomprimento de uma seqncia da forma</p> <p>filho(i), filho(filho(i)), filho(filho(filho(i))), . . .</p> <p>onde filho(i) vale 2i ou 2i+ 1.</p> <p>Os ns que tm altura zero so as folhas.</p> <p>Algoritmos p.362/434</p> <p>Altura</p> <p>A altura de um n i o maior comprimento de um caminhode i a uma folha.</p> <p>Em outras palavras, a altura de um n i o maiorcomprimento de uma seqncia da forma</p> <p>filho(i), filho(filho(i)), filho(filho(filho(i))), . . .</p> <p>onde filho(i) vale 2i ou 2i+ 1.</p> <p>Os ns que tm altura zero so as folhas.</p> <p>A altura de um n i ????.</p> <p>Algoritmos p.362/434</p> <p>Exerccio 12.A</p> <p>A altura de um n i o comprimento da seqncia</p> <p>2 i, 22 i, 23 i, . . . , 2h i</p> <p>onde 2h i m &lt; 2(h+1) i. Assim,</p> <p>2h i m &lt; 2h+1i 2h m/i &lt; lg 2h+1 h lg(m/i) &lt; h+ 1</p> <p>Portanto, a altura de i blg(m/i)c.</p> <p>Algoritmos p.363/434</p> <p>Exerccio 12.BMostre que A[1 . .m] tem no mximo dm/2h+1e ns comaltura h.</p> <p>Exemplo: Nh = nmero de ns altura h</p> <p>m bm/20+1c N0 dm/20+1e bm/21+1c N1 dm/21+1e</p> <p>16 8 8 8 4 4 417 8 9 9 4 4 518 9 9 9 4 5 519 9 10 10 4 5 520 10 10 10 5 5 521 10 11 11 5 5 622 11 11 11 5 6 623 11 12 12 5 6 624 12 12 12 6 6 6</p> <p>Algoritmos p.364/434</p> <p>SoluoProva: Exerccio 12.B</p> <p>Algoritmos p.365/434</p> <p>ResumoConsidere uma rvore representada em um vetor A[1 . . . m].</p> <p>filho esquerdo de i: 2 ifilho direito de i: 2 i+ 1pai de i: bi/2c</p> <p>nvel da raiz: 0nvel de i: blg ic</p> <p>altura da raiz: blgmcaltura da rvore: blgmcaltura de i: blg(m/i)caltura de uma folha: 0total de ns de altura h dm/2h+1e (Exerccio 12.B)</p> <p>Algoritmos p.366/434</p> <p>Heap</p> <p>Um vetor A[1 . . .m] um max-heap se</p> <p>A[bi/2c] A[i]</p> <p>para todo i = 2, 3, . . . ,m.</p> <p>De uma forma mais geral, A[j . . .m] um max-heap se</p> <p>A[bi/2c] A[i]</p> <p>para todo i = 2j, 2j + 1, 4j, . . . , 4j + 3, 8j, . . . , 8j + 7, . . ..</p> <p>Neste caso tambm diremos que a subrvore com raiz j </p> <p>um max-heap.</p> <p>Algoritmos p.367/434</p> <p>Max-heap</p> <p>Interferncia!</p> <p>PSfrag replacements</p> <p>1</p> <p>1</p> <p>2</p> <p>2</p> <p>3</p> <p>3</p> <p>4</p> <p>4</p> <p>5</p> <p>5</p> <p>6</p> <p>6</p> <p>7</p> <p>7</p> <p>8</p> <p>8</p> <p>9</p> <p>9 10</p> <p>10</p> <p>11</p> <p>11</p> <p>12</p> <p>12</p> <p>nvel</p> <p>0</p> <p>1</p> <p>2</p> <p>3</p> <p>51</p> <p>51</p> <p>46</p> <p>46</p> <p>17</p> <p>17</p> <p>34</p> <p>34</p> <p>41</p> <p>41</p> <p>15</p> <p>15</p> <p>14</p> <p>14</p> <p>23</p> <p>23</p> <p>30</p> <p>30</p> <p>21</p> <p>21 10</p> <p>10 12</p> <p>12</p> <p>Algoritmos p.368/434</p> <p>Rotina bsica de manipulao de max-heap</p> <p>PSfrag replacements</p> <p>1</p> <p>1</p> <p>2</p> <p>2</p> <p>3</p> <p>3</p> <p>4</p> <p>4</p> <p>5</p> <p>5</p> <p>6</p> <p>6</p> <p>7</p> <p>7</p> <p>8</p> <p>8</p> <p>9</p> <p>9 10</p> <p>10</p> <p>11</p> <p>11</p> <p>12</p> <p>12</p> <p>nvel</p> <p>0</p> <p>1</p> <p>2</p> <p>3</p> <p>13</p> <p>13</p> <p>46</p> <p>46</p> <p>17</p> <p>17</p> <p>34</p> <p>34</p> <p>41</p> <p>41</p> <p>15</p> <p>15</p> <p>14</p> <p>14</p> <p>23</p> <p>23</p> <p>30</p> <p>30</p> <p>21</p> <p>21 10</p> <p>10 12</p> <p>12</p> <p>Algoritmos p.369/434</p> <p>Rotina bsica de manipulao de max-heap</p> <p>PSfrag replacements</p> <p>1</p> <p>1</p> <p>2</p> <p>2</p> <p>3</p> <p>3</p> <p>4</p> <p>4</p> <p>5</p> <p>5</p> <p>6</p> <p>6</p> <p>7</p> <p>7</p> <p>8</p> <p>8</p> <p>9</p> <p>9 10</p> <p>10</p> <p>11</p> <p>11</p> <p>12</p> <p>12</p> <p>nvel</p> <p>0</p> <p>1</p> <p>2</p> <p>3</p> <p>46</p> <p>46</p> <p>13</p> <p>13</p> <p>17</p> <p>17</p> <p>34</p> <p>34</p> <p>41</p> <p>41</p> <p>15</p> <p>15</p> <p>14</p> <p>14</p> <p>23</p> <p>23</p> <p>30</p> <p>30</p> <p>21</p> <p>21 10</p> <p>10 12</p> <p>12</p> <p>Algoritmos p.370/434</p> <p>Rotina bsica de manipulao de max-heap</p> <p>PSfrag replacements</p> <p>1</p> <p>1</p> <p>2</p> <p>2</p> <p>3</p> <p>3</p> <p>4</p> <p>4</p> <p>5</p> <p>5</p> <p>6</p> <p>6</p> <p>7</p> <p>7</p> <p>8</p> <p>8</p> <p>9</p> <p>9 10</p> <p>10</p> <p>11</p> <p>11</p> <p>12</p> <p>12</p> <p>nvel</p> <p>0</p> <p>1</p> <p>2</p> <p>3</p> <p>46</p> <p>46</p> <p>41</p> <p>41</p> <p>17</p> <p>17</p> <p>34</p> <p>34</p> <p>13</p> <p>13</p> <p>15</p> <p>15</p> <p>14</p> <p>14</p> <p>23</p> <p>23</p> <p>30</p> <p>30</p> <p>21</p> <p>21 10</p> <p>10 12</p> <p>12</p> <p>Algoritmos p.371/434</p> <p>Rotina bsica de manipulao de max-heap</p> <p>PSfrag replacements</p> <p>1</p> <p>1</p> <p>2</p> <p>2</p> <p>3</p> <p>3</p> <p>4</p> <p>4</p> <p>5</p> <p>5</p> <p>6</p> <p>6</p> <p>7</p> <p>7</p> <p>8</p> <p>8</p> <p>9</p> <p>9 10</p> <p>10</p> <p>11</p> <p>11</p> <p>12</p> <p>12</p> <p>nvel</p> <p>0</p> <p>1</p> <p>2</p> <p>3</p> <p>46</p> <p>46</p> <p>41</p> <p>41</p> <p>17</p> <p>17</p> <p>34</p> <p>34</p> <p>21</p> <p>21</p> <p>15</p> <p>15</p> <p>14</p> <p>14</p> <p>23</p> <p>23</p> <p>30</p> <p>30</p> <p>13</p> <p>13 10</p> <p>10 12</p> <p>12</p> <p>Algoritmos p.372/434</p> <p>Rotina bsica de manipulao de max-heap</p> <p>PSfrag replacements</p> <p>1</p> <p>1</p> <p>2</p> <p>2</p> <p>3</p> <p>3</p> <p>4</p> <p>4</p> <p>5</p> <p>5</p> <p>6</p> <p>6</p> <p>7</p> <p>7</p> <p>8</p> <p>8</p> <p>9</p> <p>9 10</p> <p>10</p> <p>11</p> <p>11</p> <p>12</p> <p>12</p> <p>nvel</p> <p>0</p> <p>1</p> <p>2</p> <p>3</p> <p>46</p> <p>46</p> <p>41</p> <p>41</p> <p>17</p> <p>17</p> <p>34</p> <p>34</p> <p>21</p> <p>21</p> <p>15</p> <p>15</p> <p>14</p> <p>14</p> <p>23</p> <p>23</p> <p>30</p> <p>30</p> <p>13</p> <p>13 10</p> <p>10 12</p> <p>12</p> <p>Algoritmos p.373/434</p> <p>Rotina bsica de manipulao de max-heapRecebe A[1 . .m] e i 1 tais que subrvores com raiz 2i e2i+ 1 so max-heaps e rearranja A de modo que subrvorecom raiz i seja max-heap.</p> <p>MAX-HEAPIFY (A,m, i)1 e 2i2 d 2i+ 13 se e m e A[e] &gt; A[i]4 ento maior e5 seno maior i6 se d m e A[d] &gt; A[maior ]7 ento maior d8 se maior 6= i9 ento A[i] A[maior ]</p> <p>10 MAX-HEAPIFY (A,m,maior)</p> <p>Algoritmos p.374/434</p> <p>Consumo de tempoh := altura de i = blg mi cT (h) := consumo de tempo no pior caso</p> <p>linha todas as execues da linha1-3 = 3 (1)4-5 = 2 O(1)6 = (1)7 = O(1)8 = (1)9 = O(1)10 T (h 1)</p> <p>total T (h 1) + (5) + O(2)</p> <p>Algoritmos p.375/434</p> <p>Consumo de tempoh := altura de i = blg mi cT (h) := consumo de tempo no pior caso</p> <p>Recorrncia associada:</p> <p>T (h) T (h 1) + (1),</p> <p>pois altura de maior h 1.</p> <p>Soluo assinttica: T (n) O(h).</p> <p>Como h lgm, podemos dizer que:</p> <p>O consumo de tempo do algoritmo MAX-HEAPIFY O(lgm) (ou melhor ainda, O(lg mi )).</p> <p>Algoritmos p.376/434</p> <p>Consumo de tempoh := altura de i = blg mi cT (h) := consumo de tempo no pior caso</p> <p>Recorrncia associada:</p> <p>T (h) T (h 1) + (1),</p> <p>pois altura de maior h 1.Soluo assinttica: T (n) ???.</p> <p>Soluo assinttica: T (n) O(h).</p> <p>Como h lgm, podemos dizer que:</p> <p>O consumo de tempo do algoritmo MAX-HEAPIFY O(lgm) (ou melhor ainda, O(lg mi )).</p> <p>Algoritmos p.376/434</p> <p>Consumo de tempoh := altura de i = blg mi cT (h) := consumo de tempo no pior caso</p> <p>Recorrncia associada:</p> <p>T (h) T (h 1) + (1),</p> <p>pois altura de maior h 1.Soluo assinttica: T (n) O(h).</p> <p>Como h lgm, podemos dizer que:</p> <p>O consumo de tempo do algoritmo MAX-HEAPIFY O(lgm) (ou melhor ainda, O(lg mi )).</p> <p>Algoritmos p.376/434</p> <p>Construo de um max-heap</p> <p>PSfrag replacements</p> <p>1</p> <p>1</p> <p>2</p> <p>2</p> <p>3</p> <p>3</p> <p>4</p> <p>4</p> <p>5</p> <p>5</p> <p>6</p> <p>6</p> <p>7</p> <p>7</p> <p>8</p> <p>8</p> <p>9</p> <p>9 10</p> <p>10</p> <p>11</p> <p>11</p> <p>12</p> <p>12</p> <p>nvel</p> <p>0</p> <p>1</p> <p>2</p> <p>3</p> <p>14</p> <p>14</p> <p>13</p> <p>13</p> <p>34</p> <p>34</p> <p>17</p> <p>17</p> <p>15</p> <p>15</p> <p>10</p> <p>10</p> <p>46</p> <p>46</p> <p>23</p> <p>23</p> <p>12</p> <p>12</p> <p>41</p> <p>41 30</p> <p>30 21</p> <p>21</p> <p>Algoritmos p.377/434</p> <p>Construo de um max-heap</p> <p>PSfrag replacements</p> <p>1</p> <p>1</p> <p>2</p> <p>2</p> <p>3</p> <p>3</p> <p>4</p> <p>4</p> <p>5</p> <p>5</p> <p>6</p> <p>6</p> <p>7</p> <p>7</p> <p>8</p> <p>8</p> <p>9</p> <p>9 10</p> <p>10</p> <p>11</p> <p>11</p> <p>12</p> <p>12</p> <p>nvel</p> <p>0</p> <p>1</p> <p>2</p> <p>3</p> <p>14</p> <p>14</p> <p>13</p> <p>13</p> <p>34</p> <p>34</p> <p>17</p> <p>17</p> <p>15</p> <p>15</p> <p>10</p> <p>10</p> <p>46</p> <p>46</p> <p>23</p> <p>23</p> <p>12</p> <p>12</p> <p>41</p> <p>41 30</p> <p>30 21</p> <p>21</p> <p>Algoritmos p.378/434</p> <p>Construo de um max-heap</p> <p>PSfrag replacements</p> <p>1</p> <p>1</p> <p>2</p> <p>2</p> <p>3</p> <p>3</p> <p>4</p> <p>4</p> <p>5</p> <p>5</p> <p>6</p> <p>6</p> <p>7</p> <p>7</p> <p>8</p> <p>8</p> <p>9</p> <p>9 10</p> <p>10</p> <p>11</p> <p>11</p> <p>12</p> <p>12</p> <p>nvel</p> <p>0</p> <p>1</p> <p>2</p> <p>3</p> <p>14</p> <p>14</p> <p>13</p> <p>13</p> <p>34</p> <p>34</p> <p>17</p> <p>17</p> <p>15</p> <p>15</p> <p>21</p> <p>21</p> <p>46</p> <p>46</p> <p>23</p> <p>23</p> <p>12</p> <p>12</p> <p>41</p> <p>41 30</p> <p>30 10</p> <p>10</p> <p>Algoritmos p.379/434</p> <p>Construo de um max-heap</p> <p>PSfrag replacements</p> <p>1</p> <p>1</p> <p>2</p> <p>2</p> <p>3</p> <p>3</p> <p>4</p> <p>4</p> <p>5</p> <p>5</p> <p>6</p> <p>6</p> <p>7</p> <p>7</p> <p>8</p> <p>8</p> <p>9</p> <p>9 10</p> <p>10</p> <p>11</p> <p>11</p> <p>12</p> <p>12</p> <p>nvel</p> <p>0</p> <p>1</p> <p>2</p> <p>3</p> <p>14</p> <p>14</p> <p>13</p> <p>13</p> <p>34</p> <p>34</p> <p>17</p> <p>17</p> <p>15</p> <p>15</p> <p>21</p> <p>21</p> <p>46</p> <p>46</p> <p>23</p> <p>23</p> <p>12</p> <p>12</p> <p>41</p> <p>41 30</p> <p>30 10</p> <p>10</p>