Наличие определенной структуры данных

BeginningMath спросил: 28 марта 2018 в 02:29 в: algorithm

Мне интересно, может ли существовать такая структура данных в следующих критериях и времени (может быть сложной)?

, если мы получим несортированный список L, построим структуру данных из него, как это:

  • Сборка (L, X) - в момент времени O (n) мы строим структуру S из несортированного списка из n элементов.
  • Вставка (y, S ) под O (lg n) вставляем z в структуру S
  • DEL-MIN (S) - под O (lg n) удаляем минимальный элемент из S
  • DEL- MAX (S) - под O (lg n) мы удаляем максимальный элемент из S
  • DEL-MId (S) - под O (lg n) мы удаляем элемент верхней медиальной (потолочной функции) из S

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


1 ответ

Paul Hankin ответил: 28 марта 2018 в 05:17

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

Для DEL-MED, вы можете сохранить максимальную кучу элементов меньше, чем медиана, и минимальную кучу элементов, большую или равную медиане. Полное описание в этом ответе: Структура данных для поиска медианы . Обратите внимание, что в этом ответе возвращается значение floor-median, но это легко исправить. Опять же, вам нужно использовать трюк перекрестной индексации для ссылки на другие структуры данных, как в первой части. Вам также нужно будет подумать, как это обрабатывает повторяющиеся элементы, если это возможно в вашей формулировке проблемы. (При необходимости вы можете сделать это, сохранив повторяющиеся элементы как (count, value) в своей куче, но это немного усложняет перебалансировку куч при вставке / удалении).

Можно ли все это встроить в O? (п)? Да, вы можете найти медиану из n вещей за O (n) время (используя алгоритм медианы медианы), а кучи можно построить за O (n) время.

Итак, в целом, структура данных - это 4 кучи (минимальная куча всех элементов, максимальная куча всех элементов, максимальная куча пола (n / 2), самые маленькие элементы, минимальная куча потолка (n / 2) ) самые большие элементы. Все с перекрестными индексами друг к другу.

Jim Mischel ответил: 31 марта 2018 в 11:16
Вам не нужны отдельные min-heap и max-heap для DEL-MIN и DEL-MAX. Там куча мин-макс.