M10 (Mapa Mental 10)

Heaps

Heapsort

Estrutura de dados parcialmente ordenada útil na implementação de filas de prioridade

Filas de prioridade

Multiset de itens com uma característica ordenável, a prioridade do item

Operações

Deletar o item com a mais alta (ou maior) prioridade

Adicionar um novo item ao multiset

Buscar o item com a mais alta (ou maior) prioridade

A implementação eficiente de suas operações é o que faz heaps interessantes e úteis.

O Heap serve como pilar do Heapsort

Definição

Uma heap pode ser definida como uma árvore binária com chaves associadas a seus nós. Uma chave por nó.

Seguindo as condições

Propriedade de formato: A árvore binária é essencialmente completa, com todos os níveis cheios exceto o último, onde apenas algumas folhas de direita estejam ausentes.

Dominância parental ou propriedade de heap: a chave em cada nó é maior ou igual às chaves de seus filhos.

Propriedades importantes e fáceis de provar

A raiz de uma heap sempre contém seu maior elemento.

Um nó de uma heap considerada com todos seus descendantes também é uma heap em si.

Existe sempre exatamente 1 árvore binária completa com n nós. Sua altura é igual a log2 n (chão)

Uma heap pode ser implementada como array, guardando seus elementos de forma baixo-pra-cima e esquerda-para-direita. É conveniente deixar o espaço 0 na array vazio ou de sentinela, contendo um valor maior que toda a heap.

Em tal representação

As chaves dos nós parentais serão nas primeiras n/2 (chão) posições do array, enquanto as chaves folhas irão ocupar as últimas n/2 (teto) posições.

Os filhos de uma chave de posição parental i (1≤ii ≤ n/2 (chão)) irão estar nas posições 2i e 2i+1 e, correspondentemente, o pai da chave em posição i (2≤i≤n) será na posição i/2 (chão)

Podemos definir como uma array H[1..n], em que todo elemento em posição i na primeira metade da array é maior ou igual aos elementos nas posições 2i e 2i+1

Embora as ideias atrás da maioria dos algoritmos de heaps são mais fáceis de entender se pensarmos nas heaps como árvores binárias, suas verdadeiras implementações são geralmente mais simples e eficientes com arrays.

Como construir uma heap para uma lista de chaves

Construção de heap baixo-cima

Construção de heap cima-baixo

Inicializa a árvore essencialmente completa com n nós por meio de colocar as chaves na ordem dada e "heapificar" a árvore.

Começando com o último nó parental, o algoritmo checa se há dominância parental para esse nó. Se não, o algoritmo troca a chave K do nó com a chave maior de seus filhos, e checa de novo. Isso continua até a dominância parental de K é satisfeita.

Após completar a heapificação da sub-árvore enraizada no nó parental atual, o algoritmo continua repetindo o processo com o predecessor direto do nó. O algoritmo para após isso ser feito para a raiz da árvore.

Alternativa menos eficiente

Construção do heap pela inserção sucessiva de uma nova chave na heap previamente construída.

Para inserir uma nova chave K, atrele um novo nó com a chave K após a última folha do heap existente. Após isso, insira K no local apropriado na heap da seguinte forma:

Compare K com a chave de seu parente: se o parente for maior que ou igual a K, pare. Senão, troque as duas chaves e compare K com seu novo pai. Continue isso até K não ser maior que seu último parente, ou até chegar a raiz.

Não pode requerir mais comparações de chave que a altura do heap. Como a altura de uma heap de n nós é log2n, a eficiência de tempo de inserção é O(log n)

Um algoritmo de dois passos

Passo 1: construção de heap

Passo 2: deleção de máximos

Construir uma heap para a dada array

Aplicar n-1 vezes a operação de deleção de raiz à heap restante

Dessa forma, elementos de array são eliminados de forma decrescente. Mas como dentro da implementação de array de heaps um elemento sendo deletado é colocado por último, a array resultante vai ser exatamente a array original em ordem crescente.

Eficiência

A construção de heap é O(n), e a deleção de máximos é (n log n), somado tem eficiência O(n log n)

Uma análise mais detalhada mostra que a eficiência temporal é, de fato, Θ(n log n) nos piores e mais medianos casos.

Dessa forma, tem a mesma classe que mergesort, mas não requer armazenamento extra, por ser in-place.

Experimentos de tempo em arquivos aleatórios mostram que heapsort roda mais devagar que quicksort, mas consegue competir com mergesort.