Questão Q234775

Question

O heapsort é um algoritmo de ordenação em que a quantidade de elementos armazenada fora do arranjo de entrada é constante durante toda a sua execução.

Answer

O heapsort utiliza uma estrutura de dados chamada heap, para ordenar os elementos a medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada, lembrando-se sempre de manter a propriedade de max-heap.

A heap pode ser representada como uma árvore (uma árvore binária com propriedades especiais^[2]) ou como um vetor. Para uma ordenação crescente, deve ser construído um heap máximo (o maior elemento fica na raiz). Para uma ordenação decrescente, deve ser construído um heap mínimo(o menor elemento fica na raiz).

Answer

Pessoal,

Nao entendi essa, da descricao de uma implementacao do heapsort, eu tirei:

(decrease the size of the heap by one so that the previous max value will stay in its proper placement)

Isso me leva a entender que o heap size varia com as iteraçoes....

Pra mim o gabarito deveria ser: "Errado".

Answer

Tirado do livro de algoritmos do CORMEN:
"Neste capítulo, introduzimos outro algoritmo de ordenação. Como a ordenação por intercalação,
mas diferente da ordenação por inserção, o tempo de execução do heapsort é O(n lg n).
Como a ordenação por inserção, mas diferente da ordenação por intercalação, o heapsort ordena
localmente: apenas um número constante de elementos do arranjo é armazenado fora do arranjo
de entrada em qualquer instante. Desse modo, o heapsort combina os melhores atributos
dos dois algoritmos de ordenação que já discutimos."

"ordenados no local: os números são reorganizados dentro do arranjo A, com no máximo um número constante deles armazenado
fora do arranjo em qualquer instante."

SóProvas

Continue usando...

O que está incluso