Implementation (Part 1)
Lição 5 de 9 do curso Heap Sort - Série de DSA da Coddy.
Nós construiremos o Heap Sort a partir de sua operação principal.
Desafio
FácilO coração do Heap Sort é a operação sift-down. Vamos construir isso primeiro.
Escreva uma função chamada siftDown que recebe um array arr (tratado como um heap binário) e um índice i, e restaura a propriedade de max-heap naquele nó empurrando-o para baixo. Compare o nó com seus dois filhos em 2*i + 1 e 2*i + 2; se o maior filho for maior que o nó, troque-os e continue a partir da posição do filho. Retorne o array.
Por exemplo, siftDown([1, 10, 5, 3, 2], 0) retorna [10, 3, 5, 1, 2].
Experimente você mesmo
#include <stdlib.h>
int* siftDown(int* arr, int arr_size, int i, int* returnSize) {
// Escreva o código aqui
*returnSize = arr_size;
return arr;
}
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Heap Sort - Série de DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity