Pseudo Code
Lição 4 de 9 do curso Heap Sort - Série de DSA da Coddy.
siftDown(array, i, size):
loop:
largest = i
left = 2*i + 1
right = 2*i + 2
if left < size and array[left] > array[largest]: largest = left
if right < size and array[right] > array[largest]: largest = right
if largest == i: stop
swap array[i] and array[largest]
i = largest
heapSort(array):
n = length(array)
for i from n/2 - 1 down to 0: # constrói o max-heap
siftDown(array, i, n)
for end from n-1 down to 1: # extrai o máximo repetidamente
swap array[0] and array[end]
siftDown(array, 0, end)- siftDown empurra um pai muito pequeno para baixo, passando por seu filho maior, até que a propriedade de max-heap seja restaurada.
sizeé quanto do array ainda faz parte do heap. - Fase de construção: fazer o sift down em cada nó que não seja folha (do último pai, índice
n/2 - 1, até a raiz) transforma qualquer array em um max-heap. - Fase de ordenação: cada passo move o máximo atual para o final e encolhe o heap, de modo que o array é preenchido de forma ordenada a partir do final.
Experimente você mesmo
Esta lição não inclui um desafio de código.
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