Как спроектировать структуру данных, которая представляет собой смесь хеш-таблицы и кучи

Question

Мой вопрос следующий:

Имеется список triple, и они хранятся в структуре данных с именем hash_heap (я не уверен насчет имени, просто имею в виду, что оно должно быть смесью хеш-таблицы и кучи). И я надеюсь, что структура данных обеспечивает следующие методы,

index_by_first_col(key) // the method could help find the a triple stored in it by matching the first column. It expects the searching is running at constant time
get_min_by_third_col() // the method get the minimum triple sort according to the third column, it is also expects the method is running at constant time.
insert_new_elt(triple) // add new trip, running at constant time

Возможно ли реализовать такую ​​структуру данных? Я знаю, что hashtable может поддерживать первый метод, а heap может поддерживать второй и третий, но я не знаю, как их смешивать. Есть идеи?

Спасибо!

Answer 1

Существует очень простая структура данных, которая соответствует вашим заявленным требованиям.

Используйте хеш-таблицу (с ключом в первом столбце) и, кроме того, сохраняйте указатель на ваш минимальный элемент (третьим столбцом). Затем index_by_first_col - это поиск по хеш-таблице, get_min_by_third_col - это разыменование указателя, а insert_new_elt - это вставка хеш-таблицы и сравнение, чтобы определить, нужно ли обновить указатель min.

Обратите внимание, что это дает O (n) удаление (минимум), но вы не указали никаких требований к удалению.