Эффективная структура данных для deleteMin и поиска по ключевым операциям

Question

У меня есть 100 наборов объектов A, каждый набор соответствует точке запроса Qi, 1 <= i <= 100.

class A {
    int id;
    int distance;
    float x;
    float y;
}

В каждой итерации моего алгоритма я выбираю одну точку запроса Qi и извлекаю из соответствующего набора объект, имеющий минимальное значение расстояния. Затем мне нужно найти этот конкретный объект во всех 100 наборах, выполнить поиск по его идентификатору и удалить все эти объекты.

Если я использую кучу для каждого набора объектов, дешево извлечь объект с помощью MIN(distance). Однако я не смогу найти тот же объект в других кучах, которые ищут по id, потому что куча организована по значению расстояния. Кроме того, обновление кучи стоит дорого.

Другой вариант, который я рассмотрел, - это использование map<id, (distance, x, y)> для каждого набора. Этот способ поиска (операция поиска) по идентификатору дешев. Однако для извлечения элемента с минимальным значением требуется линейное время (оно должно проверять каждый элемент на карте).

Есть ли какая-либо структура данных, которую я мог бы использовать, которая эффективна для обеих необходимых мне операций?

• extract_min (расстояние)
• находка (ID)

Заранее спасибо!

Answer 1

В дополнение к включению карты, как предлагалось многими выше, вы можете заменить минимальную кучу структурой, которая имеет сложность во время выполнения, которая постоянна для извлечения min.Ваша текущая версия имеет сложность времени выполнения O (log_2 (n)) для извлечения мин.
Поскольку диапазон ваших расстояний невелик, вы можете использовать алгоритм «Массив набора».Клавиши похожи на «счетную сортировку».Поскольку у вас может быть более одного элемента в элементе массива, но вам не важен порядок элементов с одинаковым значением, вы должны использовать двусвязный список в качестве типа данных элемента массива.Статьи Эндрю Голдберга и Тарьяна, касающиеся более быстрых алгоритмов Дейкстры, обсуждают это более подробно.

Answer 2

std::map или boost::multi_index

Answer 3

Один простой подход - иметь две карты для каждого набора данных.Первый содержит все элементы данных, отсортированные по идентификатору.Второй будет multimap и отображать расстояние до идентификатора, чтобы вы могли легко определить, какому идентификатору соответствует наименьшее расстояние.Этот был бы упорядочен по расстоянию, чтобы найти минимальную дешевизну (так как он использовал бы расстояние в качестве ключа).Вы можете использовать map вместо multimap, если знаете, что расстояния всегда будут уникальными.

Answer 4

Вы можете использовать древовидную карту.