Eu tenho que fazer um projeto: Fila de prioridade representada na Árvore de pesquisa binária. É para minha classe de algoritmos. Não sei exatamente como você usaria uma árvore de pesquisa binária como uma fila de prioridade. Todos os exemplos que encontrei na internet foram sobre heaps e que "nunca se deve implementar uma fila de prioridade em um bst, mas apenas em heap". Alguém poderia me explicar o que devo fazer exatamente? Obrigado!
Respostas:
0 para resposta № 1Como uma dica, uma fila de prioridades precisa ser eficientementesuporte inserir elementos, ler o menor valor (ou maior, em uma fila de prioridade máxima) e remover o menor valor. Um BST já suporta inserções e exclusões rápidas. Então, se você tivesse todos os elementos em sua fila prioritária armazenados em um BST, como você encontraria o menor valor? Veja se você pode usar o fato de que o BST armazena seus elementos na ordem de classificação para encontrar um algoritmo muito rápido para encontrar o menor valor.