Heaps and Heapsort

Heap

é uma estrutura de dados inteligente e parcialmente ordenada que é especialmente adequada para implementar filas de prioridade

Heapsort

fila de prioridade

é um multiconjunto de itens com uma característica ordenável chamada prioridade de um item

operações

encontrar um item com a prioridade mais alta (ou seja, a maior)
excluir um item com a prioridade mais alta
adicionando um novo item ao multiset

Aplicações

  • agendamento de execuções de tarefas por sistemas operacionais de computador
  • gerenciamento de tráfego por redes de comunicação
    surgem em vários algoritmos importantes, por exemplo:
  • algoritmo de Prim;
  • algoritmo de Dijkstra;
  • codificação de Huffman;
  • aplicações branch-and-bound.
    serve como pedra angular de um algoritmo de classificação teoricamente importante chamado heapsort.

Definição

uma árvore binária com chaves atribuídas ao seu
nós, uma chave por nó, desde que as duas condições sejam atendidas

  1. A dominância parental ou propriedade de heap — a chave em cada nó é maior ou igual às chaves em seus filhos. (Esta condição é considerada automaticamente satisfeita para todas as folhas.)
  1. A propriedade de forma – a árvore binária é essencialmente completa (ou simplesmente completa), ou seja, todos os seus níveis estão cheios, exceto possivelmente o último nível, onde apenas algumas folhas mais à direita podem estar faltando.

os valores de chave em um heap são ordenados de cima para baixo

No entanto, não há ordem da esquerda para a direita nos valores de chave

eficiência da exclusão

A eficiência da exclusão é determinada pelo número de comparações de chave necessárias para “heapificar” a árvore após a troca ter sido feita e o tamanho da árvore ser reduzido em 1

eficiência de tempo de deleção está em O(log n)

um algoritmo de ordenação interessante descoberto por J. W. J. Williams

é um algoritmo de dois estágios

Estágio 1 (construção de heap): Construir um heap para um determinado array.

Estágio 2 (exclusões máximas): Aplicar a operação de exclusão de raiz n−1 vezes
para a pilha restante

Como resultado, os elementos da matriz são eliminados em ordem decrescente

Eficiência

a eficiência de tempo do heapsort se enquadra na mesma classe que a do mergesort

Experimentos de tempo em arquivos aleatórios mostram que o heapsort é executado mais lentamente do que o quicksort, mas pode ser competitivo com o mergesort.