Como posso eficiente de acompanhar o menor elemento de uma coleção?

Question

Na veia de perguntas sobre programação:suponha que exista uma coleção de objetos que podem ser comparados entre si e ordenados.O que é a forma mais eficiente para acompanhar o menor elemento da coleção como os objetos são adicionados e a menor corrente ocasionalmente removido?

Answer 1

Usando um min-heap é o melhor caminho.

http://en.wikipedia.org/wiki/Heap_(data_structure)

Ele é feito sob medida para esta aplicação.

Answer 2

Se você precisa aleatória de inserção e remoção, a melhor maneira é, provavelmente, um array ordenado.Inserções e remoções deve ser O(log(n)).

Answer 3

@Harpreet
Que não é o ideal.Quando um objeto é removido, erickson vai ter de digitalizar toda a coleção para encontrar o novo menor.

Você quer ler sobre Árvore de busca binária's.O MS tem uma boa site para começar a descer o caminho.Mas você pode querer obter um livro como Introdução aos algoritmos (Cormen, Leiserson, Rivest, Stein) se você deseja mergulho profundo.

Answer 4

Ocasionalmente, remove um Heap De Fibonacci é ainda mais rápido do que o min-heap.A inserção é O(1), e encontrar o min também é O(1).Remoção é O(log(n))

Answer 5

Se você precisa aleatória de inserção e remoção, a melhor maneira é, provavelmente, um classificados matriz.Inserções e remoções deverão ser O(log(n)).

Sim, mas você vai precisar re-classificar em cada inserir e (talvez) de cada eliminação, que, como você disse, é O(log(n)).

Com a solução proposta por Harpreet:

• você tem um S(n) passar, no começo, para encontrar o menor elemento de
• as pastilhas são O(1) a partir daí (apenas 1 comparação necessários para o já conhecido o menor elemento)
• exclui será O(n), porque você terá que re-encontrar o menor elemento (tenha em mente Big O notation é pior caso).Você também pode otimizar para verificar se o elemento a ser excluído é o (conhecido) menor, e se não, basta não fazer o re-seleção para encontrar o menor elemento.

Então, depende.Um desses algoritmos, será melhor para uma inserção pesados de caso de uso com alguns exclui, mas o outro é, em geral, mais consistente.Eu acho que seria padrão para Harpreet do mecanismo, a menos que eu sabia que o menor número deveria ser removido muitas vezes, porque o que expõe um ponto fraco em que o algoritmo.

Answer 6

Harpreet:

as inserções em que seria linear, pois você tem que mover itens para uma inserção.

Não que dependem da implementação da coleção?Se ela age como uma lista ligada, insere seria O(1), enquanto que se fosse implementado como uma matriz seria linear, como você afirmou.

Answer 7

Depende o que você precisa de seu recipiente de suporte.Um min-heap é o melhor que você pode precisar remover o min elemento em um dado momento, apesar de várias operações são não-trivial (amortizado log(n) o tempo, em alguns casos).

No entanto, se você só precisa push/pop de frente/trás, você pode apenas usar uma mindeque que atinge amortizado de tempo constante para todas as operações (incluindo findmin).Você pode fazer um scholar.google.com procura para saber mais sobre essa estrutura.Eu e um amigo, recentemente, colaborou para chegar a um muito mais fácil de compreender e de implementar a versão de um mindeque, bem.Se é isso que você está procurando eu poderia postar os detalhes para você.