Как создать структуру данных с ограничениями времени выполнения

Question

Мне нужно реализовать структуру данных, которая поддерживает удаление вставки и поиск в O (log (n)) и извлечение специального объекта в O (1). В моей структуре данных должны храниться автомобили, отсортированные по их идентификатору, и у каждого автомобиля есть поле, которое представляет время до следующей службы. Мне нужно извлечь транспортные средства, которые должны были быть следующими в O (1). Все предложения приветствуются.

Я понял, что мне нужны две отдельные структуры данных, и я подумал о том, что 1 очередь и 1 приоритетная очередь отсортированы по другим параметрам, но содержат копию того же указателя. Проблема, которую я имею, заключается в том, что когда я пытаюсь удалить из структуры «set», я остаюсь с мусором в другой структуре данных (очередь приоритетов).

Answer 1

Хэш-таблица поддерживает вставку, удаление и поиск намного лучше, чем O (log (n)). Это предполагает, что вам никогда не придется переписывать все, когда вы выращиваете стол. Трудной частью будет поиск «следующего» автомобиля в течение O (1).

В зависимости от реализации, min heap предоставит вам установку O (1) и O (log (n)) (амортизированная), а поиск минимального элемента - O (1). Удаление элемента из кучи - это операция O (log (n)), но , находящее, произвольный элемент в куче больше, чем O (log (n)).

Если бы я реализовал это, я бы использовал две отдельные структуры данных: хеш-таблицу и кучу минут. Причиной является то, что хеш-таблица обеспечивает очень быструю установку, удаление и поиск, а куча обеспечивает упорядочение на основе времени обслуживания. Единственное место, где это не соответствует вашим начатым требованиям, заключается в удалении транспортного средства, поскольку для этого требуется поиск кучи для произвольного элемента.

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