Flashcard FC268569
Qual método ordena construindo um heap máximo e extraindo repetidamente a raiz?
Algoritmos e Lógica de Programação
IDECAN · 2024
Qual método ordena construindo um heap máximo e extraindo repetidamente a raiz?
Mostrar resposta e comentário
Resposta
Heapsort.Como funciona:
Constrói um heap máximo do array (filhos de i: \(2i+1,\,2i+2\) em índice 0).
Troca a raiz com o último elemento, reduz o heap e aplica sift-down na raiz repetidamente.
Complexidade:
Construção = \(O(n)\), remoções = \(O(\log n)\) cada, total = \(O(n\log n)\).
Características:
in-place, não estável, garante \(O(n\log n)\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/266058
Conteúdo do catálogo FC Concursos · Atualizado em