estrutura de dados Heap

Jefferson Gomes de Oliveira

Estrutura de dados
Heap

Heap
A Heap é uma estrutura especializada baseada em árvores que satisfaz a seguinte propriedade:
Propriedade 1: Se B é um nó filho de A, então chave(A) ≥ chave(B).
A propriedade acima implica em que o nó raiz seja sempre o elemento com maior chave na estrutura. A estrutura acima é conhecida como max_heap. A propriedade 1 pode ser invertida para chave(A) ≤ chave(B) o que implica em que o nó raiz sempre terá o elemento com a menor chave. Neste caso, a estrutura será chamada de mim_heap.
Os principais usos da heap são na implementação eficiente de filas de prioridade, em alguns algoritmos como o Algoritmo de Djikstra, e em algoritmos de ordenação de dados tal como o algoritmo heapsort.
Curiosidade
A estrutura de dados heap não deve ser confundida com a heap que é comumente referenciada como a região de memória usada para a alocação dinâmica de memória. O termo foi originalmente usado para a estrutura de dados. No entanto, algumas linguagens de programação tal como Lisp implementavam a alocação dinâmica de memória usando esta estrutura de dados o que veio aconferir o nome a esta área de memória o nome.
A heap é geralmente implementada em um array e não requer ponteiros entre os elementos.

Operações

As operações mais comuns associadas com heaps são:
•create_heap- cria uma heap vazia
•find_max- função que dada uma heap, encontra e retorna uma copia de seu maior elemento
(Note que tal definição pressupõe uma max_heap, no caso das min_heaps a função seria melhor nomeada find_min);
•delete_max- remove o maior elemento da heap .
•increase_key- incrementa a prioridade de um dado elemento. A heap deve ser re-balanceada após tal incremento;
•decrease_key- decrementa a prioridade de um dado elemento. A heap deve ser rebalanceada após tal decremento.
•insert- insere um novo elemento na heap. A heap deve ser re-balanceada após tal decremento; •merge- compõe uma nova heap dadas duas heaps