Uma estrutura de dados eficiente que suporta Insert, Delete e MostFrequent

Suponha que tenhamos um conjunto e cada membro de seja um par de dados e chave. Queremos uma estrutura de dados que suporte as seguintes operações:$D$$D$

• Insira em ,$(d,k)$$D$
• Exclua o membro , (não é necessário pesquisar para encontrar , por exemplo, aponta para um membro em ),$e$$e$$e$$D$
• MostFrequent, que retorna um membro modo que é uma das chaves mais frequentes em (observe que a chave mais frequente não precisa ser exclusiva).$e \in D$$e.key$$D$

O que seria uma implementação eficiente dessa estrutura de dados?

Minha solução é uma pilha para as teclas e suas frequências priorizadas pelas frequências, além de uma tabela de hash em que a função hash mapeia membros com a mesma chave para o mesmo slot na tabela de hash (com ponteiros de cada parte para a outra).

Isso pode fornecer para as duas primeiras operações e para a terceira (pior caso de execução).$\Theta(\lg n)$$\Theta(1)$

Gostaria de saber se existe uma solução mais eficiente? (ou uma solução mais simples com a mesma eficiência?)

No modelo de computação baseado em comparação, você pode implementar a fila de prioridade usando uma pilha de Fibonacci em vez de uma pilha comum. Isso fornecerá os seguintes limites: tempo amortizado para inserção e O ( log n ) tempo amortizado para operações de exclusão.$\mathcal{O}(1)$$\mathcal{O}(\log n)$

Se você se afastar do modelo baseado em comparação e adotar o modelo de RAM em que as chaves são consideradas como cadeias binárias, cada uma contida em uma ou mais palavras de máquina, você poderá implementar sua fila de prioridade em . De fato, você pode obter, para as operações de inserção e exclusão, O ( $o(\log n)$e tempoO(1)para a operação findMin. Thorup provou que$\mathcal{O}(\sqrt{\log \log n})$$\mathcal{O}(1)$

Se pudermos classificar chaves no tempo S ( n ) por chave, podemos implementar uma fila de prioridade que suporte find-min em tempo constante e atualizações (inserir e excluir) no tempo S ( n ) .$n$$S(n)$$S(n)$

Veja M. Thorup. Equivalência entre filas prioritárias e classificação, 2002. in Proc. FOCS 2002

Como podemos classificar em tempo e espaço linear esperados, conforme mostrado por$\mathcal{O}(n \sqrt{\log \log n})$

Y. Han e M. Thorup. Classificação inteira em tempo esperado e espaço linear. em Proc. FOCS 2002$\mathcal{O}(n \sqrt{\log \log n})$

o limite está provado.

Você pode fazer tudo isso em tempo esperado de amortização. O truque essencial é que não precisamos de toda a potência de uma fila prioritária, pois a frequência principal muda apenas 1 em cada inserção ou exclusão.$O(1)$

Minha solução abaixo é realmente apenas sua solução com uma fila de prioridade "ineficiente" que funciona bem para este caso: uma fila de prioridade máxima implementada como uma lista de baldes de chaves duplamente vinculada tem O (1) insertMin, deleteMax, removeFromBucket e raiseKey.

Mantenha uma lista de Buckets duplamente vinculada, em que cada Bucket possui um conjunto de chaves de hash não vazio (que chamo de Coorte) e um número inteiro positivo (que chamo ValCount). Em um Balde b, cada tecla k na Coorte de b tem o mesmo número de valores exclusivos associados a ela no conjunto que você está mantendo. Por exemplo, se o seu conjunto tiver os pares (a, maçã), (a, abacate), (b, banana), (c, pepino), (d, fruta do dragão) em que as letras únicas são as teclas e as frutas são os valores, você teria dois baldes: um balde teria um ValCount de 2 e um grupo que consistisse em apenas uma chave: a. O outro Balde teria um ValCount de 1 e uma Coorte que consistisse nas três chaves b, ce ed.

A lista duplamente vinculada de Bucket deve ser mantida ordenada pelo ValCount. Será importante que possamos encontrar a cabeça e o final da lista no tempo e que possamos dividir em um novo Balde no tempo O ( 1 ) se conhecermos seus vizinhos. Sem imaginação, chamarei a lista de Buckets de BucketList.$O(1)$$O(1)$

Além do BucketList, precisamos de um SetMap, que é um mapeamento de chaves de mapeamento de hash para ValueBuckets. Um ValueBucket é um par que consiste no ValueSet (um conjunto de valores de hash não vazio) e um ponteiro não nulo para um Bucket. O ValueSet associado a uma chave k contém todos os valores exclusivos associados a k. O ponteiro de bucket associado a um ValueSet tem uma coorte igual ao tamanho do ValueSet. O Balde associado a uma chave k no SetMap também está associado à chave k no BucketList.

Em C ++:

struct Bucket {
    unsigned ValCount;
    unordered_set<Key> Cohort;
    Bucket * heavier;
    Bucket * lighter;
};
Bucket * BucketListHead;
Bucket * BucketListTail;

struct ValueBucket {
  unordered_set<Value> ValueSet;
  Bucket * bucket;
};
unordered_map<Key, ValueBucket> SetMap;

Para encontrar um par de valores-chave de frequência máxima, basta olhar para o cabeçalho do BucketList, encontrar uma chave no Cohort, procurar essa chave no SetMap e encontrar um valor no ValueSet do ValueBucket. (ufa!)

Inserir e excluir pares de valores-chave é mais complicado.

Para inserir ou excluir um par de valores-chave, primeiro insira ou exclua-o no SetMap. Isso alterará o tamanho do ValueSet, portanto, precisamos modificar o Bucket associado à chave. Os únicos Buckets que precisaremos analisar para fazer essa alteração serão os vizinhos imediatos do Bucket que a chave costumava estar. Existem vários casos aqui, e provavelmente não valem a pena ser detalhados, embora eu fique feliz para elaborar se você ainda está tendo problemas.

Pior complexidade

$\mathcal{O}(1)$

$\mathcal{O}(1)$

$\mathcal{O}(1)$

$\mathcal{O}(\log \log n)$

$\mathcal{O}(n)$

Prova

$[0 , N )$ $\mathrm{\mathcal{O}(log\ log\ min \{n, N\})}$

Que é estabelecido com uma combinação de:

$\tau(n, N)$ $n$$[0 , N)$ $\tau ( n, N ) \le τ ( N, N)$$\tau$

e:

$n$$[0 , N)$$\mathrm{\mathcal{O}(1 + log\ log\ n − log\ log\ q)}$$q$

Referência

Thorup, Mikkel. “Filas de prioridade inteira com chave decrescente no tempo constante e o problema dos caminhos mais curtos de fonte única.” STOC '03. Nova York, NY, EUA: ACM, 2003.