Лучшая структура данных для поиска по максимальным значениям и идентификатору?

Question

У меня довольно много записей фиксированного размера. Каждая запись имеет много полей, ID и значение среди них. Мне интересно, какая структура данных будет лучше, чтобы я мог

1. очень быстро найти запись по идентификатору (уникальному),

2. перечислить 100 записей с самыми большими значениями.

Макс-куча кажется работой, но далека от совершенства; у вас есть более разумное решение?

Спасибо.

Answer 1

Гибридная структура данных, скорее всего, будет лучшей. Для эффективного поиска по идентификатору хорошая структура - это, очевидно, хеш-таблица. Для поддержки итерации топ-100 хорошо подходит max-heap или двоичное дерево. При вставке и удалении вы просто делаете операцию на обеих структурах. Если 100 для случая итерации фиксировано, итерация происходит часто, и вставки / удаления не сильно перекошены в топ-100, просто оставьте топ-100 в виде отсортированного массива с переполнением до максимальной кучи. Это не изменит сложность структуры big-O, но даст действительно хорошее постоянное ускорение для случая итерации.

Answer 2

Я знаю, что вам нужен алгоритм псевдокода, но в Java, например, я бы использовал TreeSet, добавив все записи по ID, парам значений.

Дерево добавит их, отсортированные по значению, поэтому запрос первых 100 даст вам первые 100. Получение по идентификатору будет простым.

Я думаю, что алгоритм называется Binary-Tree или Balanced Tree, не уверен.

Answer 3

Максимальная куча будет соответствовать второму требованию, но для первого лучше использовать хеш-карты или сбалансированные деревья поиска. Сделайте выбор исходя из частоты этих операций. Как часто вам нужно находить один элемент по идентификатору и как часто вам нужно получать первые 100 элементов?

Псевдокод:

add(Item t)
{
    //Add the same object instance to both data structures
    heap.add(t);
    hash.add(t);
}
remove(int id)
{
    heap.removeItemWithId(id);//this is gonna be slow
    hash.remove(id);
}
getTopN(int n)
{
    return heap.topNitems(n);
}
getItemById(int id)
{
    return hash.getItemById(id);
}
updateValue(int id, String value)
{
    Item t = hash.getItemById(id);
    //now t is the same object referred to by the heap and hash
    t.value = value;
    //updated both.
}