heapsort

623 palavras 3 páginas
Em ciência da computação, um heap é uma estrutura de dados organizada como árvore binária balanceada, seguindo algumas regras. Este pode ser implementado em um arranjo, para que ele seja acessado como uma árvore binária, usando as seguintes operações1 2 :

PAI(i) return i/2 ESQUERDA(i) return i*2 DIREITA(i) return i*2 + 1

Um arranjo acessado como uma arvore binaria balanceada.1
Se estiver bem implementado estas são macros ou procedimentos "inline".2 Estas operações podem ser executadas rapidamente usando operações bit a bit.2 Para o filho esquerdo desloca os bits a esquerda, para o direito desloca os bits para a esquerda e aplica a operação "ou" com 1.2 Para encontrar o pai, desloca um bit a direita.2 A vantagem de usar operações bit a bit, é que cada uma delas usa apenas um clock do processador, sendo altamente eficiente.2

Índice [esconder]
1 Características
2 Operações
2.1 Inserção
2.2 Remoção
3 Implementações
3.1 Implementação em C++
4 Utilização
5 Referências
6 Ver também
7 Bibliografia
Características[editar | editar código-fonte]
Existem dois tipos de heaps: Os heaps de máximo (max heap), em que o valor de todos os nós são menores que os de seus respectivos pais; e os heaps de mínimo (min heap), em que o valor todos os nós são maiores que os de seus respectivos pais. Assim, em um heap de máximo, o maior valor do conjunto está na raíz da árvore, enquanto no heap de mínimo a raíz armazena o menor valor existente.

A árvore binária do heap deve estar completa até pelo menos seu penúltimo nível e, se o seu último nível não estiver completo, todos os nós do último nível deverão estar agrupados à esquerda.1

Operações[editar | editar código-fonte]
As operações mais comuns em heaps são:

Inserção[editar | editar código-fonte]
Inserção: Adicionar um novo nó ao heap..
Codigo em Java

public void insertItem(Object k, Object e) throws InvalidKeyException { if(!comp.isComparable(k)) throw new

Relacionados

  • Heapsort
    1787 palavras | 8 páginas
  • Heapsort
    1157 palavras | 5 páginas
  • Heapsort
    1174 palavras | 5 páginas
  • ordenacao heapsort
    2340 palavras | 10 páginas
  • Algoritmo HeapSort
    1677 palavras | 7 páginas
  • Avaliação empírica de desempenho dos algoritmos de ordenação: quicksort, mergesort e heapsort
    2840 palavras | 12 páginas
  • Heap sort
    533 palavras | 3 páginas
  • CP Teoria Ordenacao Parte2 2 C pia
    2010 palavras | 9 páginas
  • Apostila Paulo Eustáquio
    1387 palavras | 6 páginas
  • Estudante
    1297 palavras | 6 páginas