Quando devo usar um heap?

Além da resposta óbvia de uma Fila de prioridade, quando um heap seria útil em minhas aventuras de programação?

Use-o sempre que precisar de acesso rápido ao maior (ou menor) item, porque esse item sempre será o primeiro elemento na matriz ou na raiz da árvore.

No entanto, o restante da matriz é mantido parcialmente sem classificação. Assim, o acesso instantâneo só é possível ao maior (menor) item. As inserções são rápidas, por isso é uma boa maneira de lidar com eventos ou dados recebidos e sempre ter acesso aos primeiros / maiores.

Útil para filas prioritárias, programadores (onde o primeiro item é desejado), etc ...

Um heap é uma árvore em que o valor de um nó pai é maior do que qualquer um de seus nós descendentes.

Se você pensar em um heap como uma árvore binária armazenada em ordem linear por profundidade, com o nó raiz primeiro (depois os filhos desse nó, depois os filhos desses nós); então os filhos de um nó no índice N estão em 2N + 1 e 2N + 2. Esta propriedade permite acesso rápido por índice. E, como os heaps são manipulados por nós de troca, isso permite a classificação no local.

Pilhas são estruturas destinadas a permitir acesso rápido ao mínimo ou máximo .

Mas por que você quer isso? Você pode apenas verificar cada entrada em add para ver se é o menor ou o maior. Desta forma, você sempre tem o menor ou o maior em tempo constante O(1).

A resposta é porque os heaps permitem que você extraia o menor ou o maior e conheça rapidamente o PRÓXIMO menor ou maior . É por isso que é chamada de Fila de prioridade.

Exemplo do mundo real (mundo não muito justo, no entanto):

Suponha que você tenha um hospital no qual os pacientes são atendidos com base na idade. Os mais velhos são sempre atendidos primeiro, não importando quando ele entrou na fila.

Você não pode simplesmente acompanhar o mais velho porque se você puxá-lo para fora, você não saberá o próximo mais velho. Para resolver este problema hospitalar, você implementa um heap máximo . Este heap é, por definição, parcialmente ordenado. Isso significa que você não pode classificar os pacientes pela idade, mas sabe que os mais velhos estão sempre no topo, então você pode puxar um paciente em tempo constante O(1)e reequilibrar a pilha em tempo de registro O(log N).

Exemplo mais sofisticado:

Suponha que você tenha uma sequência de inteiros e deseja rastreá-los median. A mediana é o número que está no meio de uma matriz ordenada.

Exemplo:

[1, 2, 5, 7, 23, 27, 31]

No caso acima, 7é a mediana porque o array contendo os números menores [1, 2, 5]é do mesmo tamanho daquele que contém os números maiores [23, 27, 31]. Normalmente, se a matriz tem um número ímpar de elementos, a mediana é a média aritmética dos 2 elementos no meio, por exemplo (5 + 7)/2.

Agora, como você monitora a mediana? Por ter 2 heaps , um heap mínimo contendo os números menores que a mediana atual e um heap máximo contendo os números maiores do que a mediana atual. Agora, se esses heaps estiverem sempre equilibrados, os 2 heaps conterão o mesmo número de elementos ou um terá 1 elemento a mais que o outro, o máximo.

Ao adicionar um novo elemento à sequência, se o número for menor que a mediana atual, você o adiciona ao heap mínimo, caso contrário, adiciona-o ao heap máximo. Agora, se os heaps estiverem desequilibrados (um heap tem mais de 1 elemento a mais que o outro), você puxa um elemento do heap maior e adiciona ao menor. Agora eles estão equilibrados.

A característica de um heap é que ele é uma estrutura que mantém os dados semi-ordenados; portanto, é uma boa troca entre o custo de manter um pedido completo e o custo de pesquisar no caos aleatório. Essa característica é usada em muitos algoritmos, como seleção, ordenação ou classificação.

Outra característica útil de um heap é que ele pode ser criado no local a partir de um array!

Também é bom para algoritmos de seleção (encontrando o mínimo ou máximo)

a qualquer momento ao classificar uma lista temporária, você deve considerar muitos.

Você pode usar um minHeap ou maxHeap quando quiser acessar os elementos menores e maiores, respectivamente.