Para localizar o elemento mais antigo / mais recente em um heap

5

Eu quero encontrar o elemento mais antigo / mais recente adicionado a um monte de tamanho k. Em qualquer ponto de tempo, se eu tiver que encontrar o elemento mais antigo na pilha, há alguma abordagem com O (1) espaço e O (1) tempo.

Eu estava pensando em uma abordagem de ter uma fila do mesmo tamanho que a do heap e incluir todo o elemento na fila conforme eles são adicionados ao heap. Isso produz uma solução de tempo constante, mas isso requer um espaço O (k) extra. Eu gostaria de saber se esse problema pode ser resolvido com espaço constante.

    
por redDragon 08.09.2014 / 00:23
fonte

3 respostas

3

Você pode usar uma Fila de prioridade de final duplo para isso. Há vários métodos de implementação disponíveis e a estrutura é rotineiramente disponível em muitas bibliotecas. A maioria das bibliotecas Java o chamam de MinMaxPriorityQueue. Ele oferece O (1) recuperação de Min e Max (mais recente / mais antigo) no tempo O (1).

Para preencher seu requisito de espaço, você precisará usar um heap de intervalo em que cada nó tenha dois valores. A contabilidade é um pouco complicada, mas não mais lenta que o normal.

    
por 08.09.2014 / 00:34
fonte
2

Se você mantiver uma estrutura de dados separada ao lado do seu heap, isso provavelmente resolveria seu problema. Essa é a abordagem que o LinkedHashMap usa (uma lista encadeada ao lado HashMap) para permitir um cache LRU e uma ordenação bem conhecida das entradas no LinkedHashMap (ordem de inserção) (grepcode LinkedHashMap.Entry ).

Essa estrutura de dados seria semelhante a um Deque ou algo semelhante e é ordenado por ordem de inserção. Nenhum outro pedido é imposto a essa estrutura.

O maior problema em fazer isso, porém, é que as duas estruturas (o heap e o deque) não estão sincronizadas, uma teria que fazer manutenção de livros para remover do deque quando algo é removido do heap.

Uma abordagem para isso seria usar uma referência fraca (Java Referência , C # WeakRefrence class). Quando você percorre o deque, você consultará a Referência para get() para ver se existe realmente ali, e, em caso afirmativo, retorne, caso contrário, descarte esse elemento no deque e continue andando na lista até encontrar um Referência que tem um objeto anexado a ele.

A pegadinha aqui é que, se você estiver apontando para o objeto para o qual o heap está apontando, é possível que alguma outra parte do código tenha segurado o objeto e você pense que ainda está no heap. .

Para evitar isso, o deque deve apontar para o elemento heap, em vez do objeto para o qual o elemento heap está apontando, e ficar muito limpo com a remoção do elemento do heap quando ele for descartado (e não permitir que ele escape fora do heap - exceto para o deque (que provavelmente deve estar dentro do heap)). Admito não saber quanto tempo a Referência ainda apontará para algo e que condições são necessárias para deterministicamente esclarecê-la.

Isso permitiria ao coletor de lixo fazer o trabalho para você de manter livros. O trade off é, em vez de cada vez que a inserção ou remoção está sendo feita a partir do heap e da manutenção de livros sendo feita, a manutenção de livros é feita quando o deque é pesquisado ou espiado. Qual o caminho que o trade off vai é algo a considerar com base na inserção, remoção e pesquisa que o aplicativo faz do heap.

Uma ideia de manter outra estrutura de dados dentro do heap pode permitir questões de referências determinísticas. Se você tiver um HashMap no heap que contém todos os objetos também (embora note que ele não contém cópias deles faz suas próprias referências strongs aos objetos). Quando algo é adicionado ou removido do heap, ele também é adicionado ou removido do HashMap. Assim, o deque, em vez de manter referências fracas ao objeto, contém uma strong referência. Quando o deque é pesquisado, ele verifica o HashMap para ver se o objeto ainda está no heap.

De qualquer maneira, o que isso em última análise fornece é um deque de tal forma que o primeiro elemento retornado do deque seja o mais antigo no heap, e o último elemento retornado do deque é o mais novo objeto no heap.

    
por 08.09.2014 / 05:07
fonte
1

Eu copiei minha resposta desta pergunta: Que estrutura de dados posso usar para implementar uma fila de prioridades de dois terminais com inserção (n) de log (e)? Eu a repeti aqui porque essas perguntas realmente não parecem duplicações, mas simplesmente duas questões que podem ser - mas não precisam ser - resolvidas com a mesma técnica:

Aqui está o que eu fiz para uma implementação de lista livre de alocador de bloco que precisava de uma fila de prioridades de final duplo:

  • Use algoritmos padrão de árvore vermelho-preto , com um aprimoramento pequeno :
  • Durante a inserção, rastreie o elemento mínimo e máximo na árvore, à medida que você faz inserções ou exclusões. Isso só adiciona no máximo comparações O (log n) como sobrecarga durante o processo de inserção O (log n), portanto, não altera a complexidade geral do algoritmo.

Isso produz:

  • O (log n): inserção
  • O (1): find-min e delete-min
  • O (1): find-max e delete-max

Como essas eram as únicas operações que eu precisava para o meu aplicativo em particular, essa era praticamente a melhor estrutura de dados possível. Mesmo se você precisasse de outras operações de filas prioritárias (como mudança de prioridades, etc) praticamente tudo ainda seria o pior caso (log n) por causa da árvore vermelho-preto.

O motivo pelo qual você obtém O (1) tanto para find-min / max quanto para delete-min / max é que você acompanhou o elemento mínimo e máximo durante a inserção, para que possa encontrá-lo imediatamente, eliminando oO (log n) para a pesquisa. Em seguida, o algoritmo de árvore vermelho-preto garante operações O (1) para reequilibrar a árvore após o elemento ser removido. (Esta é uma propriedade bem conhecida e muito importante de árvores vermelho-preto. Este não seria o caso da maioria das outras árvores de pesquisa binária, como árvores AVL, que requerem operações O (log n) durante o reequilíbrio.)

    
por 25.11.2015 / 05:45
fonte