Implementation (Part 2)
Lição 6 de 9 do curso Heap Sort - Série de DSA da Coddy.
Agora combinamos a construção do heap e a extração repetida do máximo.
Desafio
MédioAgora junte tudo no algoritmo completo.
Escreva uma função chamada heapSort que recebe um array de inteiros e o retorna ordenado em ordem crescente.
Primeiro, construa um max-heap fazendo o sift down de cada nó que não seja folha, do índice n/2 - 1 até 0. Em seguida, troque repetidamente a raiz (o maior valor) pelo último elemento do heap, diminua o tamanho do heap em um e faça o sift down da nova raiz.
Use um auxiliar de sift-down que receba o
sizeatual do heap, para que você possa diminuir o heap conforme avança.
Experimente você mesmo
#include <stdlib.h>
int* heapSort(int* arr, int arr_size, 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