Aqui está uma descrição da estrutura de dados:

Opera como um mapa normal comget, puteremove métodos, mas tem umsort método que pode ser chamado para classificar o mapa. No entanto, o mapalembra-se sua estrutura ordenada, de modo que chamadas subsequentes para classificar podem ser muito mais rápidas (se a estrutura não mudar muito entre as chamadas parasort).

Por exemplo:

Eu chamo oput método 1.000.000 vezes.
Eu chamo osort método.
Eu chamo oput método 100 mais vezes.
Eu chamo osort método.

A segunda vez que eu chamo osort O método deve ser uma operação muito mais rápida, pois a estrutura do mapa não mudou muito. Observe que o mapa não precisa manter a ordem classificada entre as chamadas parasort.

Eu entendo que pode não ser possível, mas eu estou esperando por O (1)get, puteremove operações. Algo comoTreeMap fornece o custo de tempo O (log (n)) garantido para essas operações, mas sempre mantém uma ordem classificada (nãosort método).

Então, qual é o design dessa estrutura de dados?

Editar 1 - retornando as entradas do top-K

Embora eu goste de ouvir a resposta para o caso geral acima, meu caso de uso ficou mais específico: eu não preciso da coisa toda ordenada; apenas os elementos K superiores.

Estrutura de dados para devolver eficientemente otop-K entradas de uma tabela de hash (mapa, dicionário)

Obrigado!