Respostas do Capítulo

HeapSort:.

6

2

10

1

9

4

2

5

7

3

[pic 1][pic 2][pic 3]

6

2

10

1

9

4

2

5

7

3

[pic 4][pic 5]

[pic 6]

[pic 7][pic 8]

6

2

10

1

9

4

2

5

7

3

[pic 9][pic 10][pic 11]

[pic 12][pic 13]

[pic 14]

6

2

10

1

9

4

2

5

7

3

[pic 15][pic 16]

[pic 17][pic 18][pic 19][pic 20]

[pic 21]

[pic 22]

6

2

10

1

9

4

2

5

7

3

[pic 23][pic 24][pic 25][pic 26]

[pic 27][pic 28][pic 29]

[pic 30][pic 31][pic 32]

6

2

10

1

9

4

2

5

7

3

[pic 33][pic 34][pic 35][pic 36][pic 37][pic 38][pic 39]

[pic 40][pic 41]

[pic 42]

[pic 43][pic 44]

6

2

10

1

9

4

2

5

7

3

[pic 45][pic 46][pic 47][pic 48][pic 49][pic 50][pic 51][pic 52][pic 53][pic 54][pic 55]

[pic 56]

[pic 57]

[pic 58]

6

2

10

1

9

4

2

5

7

3

[pic 59][pic 60][pic 61][pic 62][pic 63][pic 64][pic 65][pic 66][pic 67][pic 68][pic 69][pic 70][pic 71][pic 72]

[pic 73]

[pic 74]

6

2

10

1

9

4

2

5

7

3

[pic 75][pic 76][pic 77][pic 78][pic 79][pic 80][pic 81][pic 82][pic 83][pic 84][pic 85][pic 86][pic 87][pic 88][pic 89]

[pic 90]

[pic 91][pic 92]

6

2

10

1

9

4

2

5

7

3

[pic 93][pic 94][pic 95][pic 96][pic 97][pic 98][pic 99][pic 100][pic 101][pic 102][pic 103][pic 104]

[pic 105][pic 106][pic 107][pic 108][pic 109][pic 110][pic 111][pic 112]

Agora que o heap foi criado, precisamos construir um heap mínimo (onde o menor elemento fica na raiz), visto que queremos ordenar de forma não- crescente.

1

2

2

5

3

4

10

6

7

9

[pic 113][pic 114][pic 115][pic 116][pic 117][pic 118][pic 119][pic 120][pic 121][pic 122][pic 123][pic 124][pic 125][pic 126][pic 127][pic 128][pic 129][pic 130]

[pic 131]

Perceba que cada uma das raízes possui o menor elemento de sua respectivas subárvores .  Agora mudamos o primeiro e último elemento e apagamos o último elemento, e criamos um heap mínimo de novo.  O processo irá se repetir até a ordenação acontecer.