Implementando fila de prioridade usando heap máximo vs BST balanceado

Jan 25 2021

BST balanceado e heap máximo executam inserção e exclusão O(logn). No entanto, encontrar o valor máximo em um heap máximo é O(1)apenas O(logn)um BST balanceado.

Se removermos o valor máximo em um heap máximo, será necessário O(logn)porque é uma operação de exclusão.

No BST balanceado, excluir o elemento máximo = encontrar o valor máximo + excluir; é igual a logn + logn se reduz a O(logn). Portanto, mesmo a exclusão do valor máximo no BST balanceado é O(logn).

Eu li que uma aplicação de heap máximo é uma fila de prioridade e seu objetivo principal é remover o valor máximo para cada operação de desenfileiramento. Se a exclusão do elemento max for O(logn)tanto para o heap máximo quanto para o BST balanceado, tenho as seguintes perguntas

  • Qual é a finalidade de um heap máximo na fila de prioridade apenas porque é fácil de implementar em vez de usar o BST balanceado totalmente pesquisável?

  • Como não há cálculo do fator de equilíbrio, o heap máximo pode ser chamado de árvore binária desequilibrada.

  • Cada BST balanceado pode ser usado como uma fila de prioridade e que também pode ser pesquisada, no O(logn)entanto, a pesquisa de heap máximo está O(n)correta?

Todas as complexidades de tempo são calculadas para o pior caso. Qualquer ajuda é muito apreciada.

Respostas

2 trincot Jan 25 2021 at 20:05

Qual é a finalidade de um heap máximo na fila de prioridade apenas porque é fácil de implementar em vez de usar o BST balanceado totalmente pesquisável?

Algumas vantagens de um heap são:

  • Dada uma matriz de entrada não triados, uma pilha pode ainda ser construído em O (n) de tempo , enquanto um BST precisa O (nlogn) tempo .

  • Se a entrada inicial for um array, esse mesmo array pode servir como heap, o que significa que nenhuma memória extra é necessária para ele. Embora alguém possa pensar em maneiras de criar um BST usando os dados in-loco no array, seria muito estranho (para tipos primitivos) e geraria mais sobrecarga de processamento. Um BST geralmente é criado do zero, copiando os dados para os nós à medida que são criados.

    Fato interessante: um array classificado também é um heap, portanto, se for sabido que a entrada está classificada, nada precisa ser feito para construir o heap.

  • Um heap pode ser armazenado como uma matriz sem a necessidade de armazenar referências cruzadas , enquanto um BST geralmente consiste em nós com referências à esquerda e à direita. Isso tem pelo menos duas consequências:

    • A memória usada para um BST é cerca de 3 vezes maior do que para um heap.
    • Embora várias operações tenham a mesma complexidade de tempo para heap e BST, a sobrecarga para adaptar um BST é muito maior, de modo que o tempo real gasto nessas operações é um fator (constante) maior no caso do BST.

Como não há cálculo do fator de equilíbrio, o heap máximo pode ser chamado de árvore binária desequilibrada.

Uma pilha é, na verdade, uma árvore binária completa , por isso é sempre tão equilibrada quanto pode ser: as folhas sempre serão posicionadas no último ou no último nível. Um BST de auto-equilíbrio (como AVL, vermelho-preto, ...) não pode bater aquele alto nível de equilíbrio, onde você frequentemente terá folhas ocorrendo em três níveis ou até mais.

Cada BST balanceado pode ser usado como uma fila de prioridade e que também pode ser pesquisada em O (logn), no entanto, a pesquisa de heap máximo está O (n) correto?

Sim isso é verdade. Portanto, se o aplicativo precisa do recurso de pesquisa, um BST é superior.

2 SerejaBogolubov Jan 25 2021 at 16:53

Qual é a finalidade de um heap máximo na fila de prioridade apenas porque é fácil de implementar em vez de usar o BST balanceado totalmente pesquisável?

Não. O heap máximo se ajusta melhor, pois é cuidadosamente instrumentado para retornar o próximo elemento (respeitando a prioridade) o mais rápido possível, no tempo O (1). Isso é o que você deseja da fila de prioridade mais simples possível.

Como não há cálculo do fator de equilíbrio, o heap máximo pode ser chamado de árvore binária desequilibrada.

Não. Também existe um equilíbrio. Para encurtar a história, o equilíbrio de um heap é feito por operações shift-up ou shift-down (troca de elementos que estão fora de serviço).

Cada BST balanceado pode ser usado como uma fila de prioridade e que também pode ser pesquisada em O (logn), no entanto, a pesquisa de heap máximo está O (n) correto?

Isso! Bem como a lista vinculada pode ser usada ou matriz. Só vai ser mais caro em termos de notação O e muito mais lento na prática.