-
Algoritmo Heapsort: tem tempo de execução de um algoritmo de ordenação por intercalação, e faz as suas operações localmente, sempre apenas um número constante de elementos é armazenados fora da estrutura de dados, como é feito o algoritmo por inserção. Mas o que ele tem de interessante é a forma que ele arranja os dados para depois ordená-los, ele utiliza uma estrutura chamada de heap ou monte, que é uma arvore binária que é extremamente importante para vários conceitos e problemas computacionais, pois depois de ordenados os dados, podemos, por exemplo, saber em que nível da árvore se encontra determinado item, operações sobre arvores binárias são conceitos muito importantes para outras estruturas como grafos.
-
O herap sort utiliza a ordenação por seleção o seu desempenho no pior caso é melhor que o desempenho no pior caso do quick sort. o hearp sort apresenta em todos os casos ( melhor, médio e pior) o desempenho de O( n log n) e o quick sort no pior caso apresenta O(n2). A ordenação de insert sort no pior caso apresenta a ordenação O(n2).
-
Basicamente o Heapsort insere todos os elementos em uma árvore binária. Em seguida vai removendo um a um os elementos da árvore já ordenados. A inserção em árvore binária já contempa o ordenamento implícito.
Quadro comparativo
http://screencast.com/t/MjA0NzFlN
Simulação
http://www.schau-online.de/projects/heapsort/
-
Seleção em Árvore (HeapSort): Utiliza uma estrutura de árvore binária para
a ordenação. A ordenação é realizada em duas fases:1ª fase:
Monta-se uma árvore binária (heap) contendo todos os elementos do
vetor de forma que o valor contido em qualquer nodo seja maior do que
os valores de seus sucessores. A árvore binária é estruturada no próprio
vetor da seguinte forma:
a. sucessor à esquerda de i : 2i (se 2i < n)
b. sucessor à direita de i : 2i + 1 (se 2i + 1 < n)
Transformação da árvore num heap: é realizada do menor nível até a raiz,
trocando-se cada nodo com o maior de seus sucessores imediatos.
Repete-se este processo até cada nodo ser maior que seus sucessores
imediatos.
2ª fase:
Após a formação do heap segue-se a fase de classificação propriamente
dita, na qual o valor que está na raiz da árvore (maior valor contido na
árvore) é colocado na sua posição correta, trocando-o com o elemento
de maior índice da árvore (a árvore fica com 1 elemento a menos). Este
novo elemento colocado na raiz pode violar a propriedade do heap, de
modo que deve-se restaurar o heap novamente. Este procedimento é
repetido até que a árvore fique com um único elemento.
-
Pessoal deêm uma conferida no vídeo do youtube, uma animação de como funciona o heap:
http://www.youtube.com/watch?v=0VzYHiMXZq0&feature=related
-
b) A estrutura de dados que utiliza, chamada heap, pode ser interpretada como uma árvore binária.
-
A estrutura de dados heap, que é eficiente para a implementação do método de ordenação heapsort, consiste em uma árvore binária completa e sua implementação mais simples ocorre na forma de array.
Letra B
-
Gabarito B
Heapsort - utiliza uma estrutura de dados chamada heap, para ordenar os elementos à 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 ou como Vetor.
"Retroceder Nunca Render-se Jamais !"
Força e Fé !
Fortuna Audaces Sequitur !
-
b-
In computer science, a heap is a tree-based data structure which is an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node.
https://en.wikipedia.org/wiki/Heap_(data_structure)