Мягкая куча

В информатике — мягкая куча это вариант простой структуры данных кучи , которая имеет постоянную амортизированную временную сложность для 5 типов операций. Это достигается путем тщательного «искажения» (увеличения) ключей не более чем постоянного числа значений в куче.

Определение и производительность

Операции с постоянным временем: ^[1]^[2]

create ( S ): создать новую мягкую кучу
вставить ( S , x ): вставить элемент в мягкую кучу.
meld ( S , S' ): объединить содержимое двух мягких куч в одну, уничтожив обе.
delete ( S , x ): удалить элемент из мягкой кучи.
findmin ( S ): получить элемент с минимальным ключом в мягкой куче.

Другие кучи, такие как кучи Фибоначчи, достигают большинства этих границ без каких-либо повреждений, но не могут обеспечить постоянную границу времени для критической операции удаления . Величиной коррупции можно управлять выбором параметра. $\varepsilon$ , но чем меньше это значение, тем больше времени требуется на вставки: выраженное с использованием нотации Big-O , амортизированное время будет $O(\log 1/\varepsilon )$ для частоты ошибок $\varepsilon$ . ^[1]^[2] Некоторые версии мягких куч позволяют операциям создания , вставки и объединения в худшем случае выполнять постоянное время, обеспечивая амортизированную, а не наихудшую производительность только для findmin и delete. ^[3] Как и в случае с сортировкой сравнением , эти алгоритмы получают доступ к ключам только путем сравнения; если разрешены арифметические операции над целочисленными ключами, то зависимость времени от $\varepsilon$ можно свести к $O(\log \log 1/\varepsilon )$ или (с рандомизацией) ${\textstyle O({\sqrt {\log \log 1/\varepsilon }})}$ . ^[4]

Точнее, гарантия ошибки, обеспечиваемая мягкой кучей, заключается в следующем: каждая мягкая куча инициализируется параметром $\varepsilon$ , выбранный между 0 и 1/2. Тогда в любой момент времени оно будет содержать не более $\varepsilon \cdot n$ поврежденные ключи, где $n$ — это количество элементов, вставленных на данный момент. Обратите внимание, что это не гарантирует, что только фиксированный процент ключей, находящихся в данный момент в куче, будет поврежден: в неудачной последовательности вставок и удалений может случиться так, что все элементы в куче будут иметь поврежденные ключи. Точно так же нет никакой гарантии, что в последовательности элементов, извлеченных из кучи с помощью findmin и delete , только фиксированный процент будет иметь поврежденные ключи: в неудачном сценарии из кучи извлекаются только поврежденные элементы. Когда ключ поврежден, значение, сохраненное для него в программной клавише, превышает его первоначально заданное значение; коррупция никогда не сможет уменьшить ценность какого-либо ключа. Операция findmin находит минимальное значение среди сохраненных в данный момент ключей, включая поврежденные. ^[1]^[2]

Мягкая куча была разработана Бернаром Шазелем в 2000 году. Термин «коррупция» в структуре является результатом того, что Шазель назвал «совместным использованием автомобилей» в мягкой куче. Каждый узел в мягкой куче содержит связанный список ключей и один общий ключ. Общий ключ — это верхняя граница значений ключей в связанном списке. Как только ключ добавляется в связанный список, он считается поврежденным, поскольку его значение больше никогда не будет актуальным ни в одной из операций с мягкой кучей: сравниваются только общие ключи. Именно это делает мягкие кучи «мягкими»; нельзя быть уверенным, что какая-либо конкретная ценность, заложенная в него, будет искажена. Целью этих искажений является эффективное снижение информационной энтропии данных, позволяя структуре данных преодолеть теоретические информационные барьеры, касающиеся кучи. ^[1]

Приложения

Несмотря на свои ограничения и непредсказуемый характер, мягкие кучи полезны при разработке детерминированных алгоритмов. Например, они использовались для достижения наилучшей на сегодняшний день сложности поиска минимального остовного дерева . ^[5] Другие проблемы, эффективное решение которых было упрощено с помощью мягких куч, включают в себя поиск $k$ наименьший элемент в нескольких классах структурированных наборов значений, включая деревья с кучей, отсортированные матрицы и суммы . ^[6]

Другим простым примером является алгоритм выбора , позволяющий найти $k$ самый маленький из группы $n$ цифры: ^[1]

Инициализировать мягкую кучу с частотой ошибок $1/3$ , что позволяет повредить не более 33% вставленных ключей.
Вставить все $n$ элементы в кучу.
Повторить $n/3$ раз: выполните операцию findmin и удалите возвращаемый ключ.
Позволять $L$ быть удаленным элементом, правильный ключ которого является наибольшим.
Сравнивать $L$ всем заданным элементам, разбейте их на подмножество меньше, чем $L$ и подмножество больше, чем $L$ , размещая элементы, равные $L$ в первое подмножество, если они были удалены, и во второе подмножество в противном случае.
Рекурсивно вызвать тот же алгоритм выбора в подмножестве, содержащем $k$ самый маленький.

После этапа сравнения алгоритма первое из двух подмножеств содержит все удаленные ключи, поэтому оно включает как минимум $n/3$ элементы.Среди $2n/3$ элементы, которые не были удалены, максимум $n/3$ испорчены, так что по крайней мере $n/3$ являются неповрежденными. Все эти неповрежденные и неудаленные элементы должны принадлежать второму подмножеству, поскольку они больше или равны значению мягкой кучи (возможно, поврежденному) $L$ , что, в свою очередь, больше истинного значения $L$ . Таким образом, оба подмножества содержат от 33% до 66% элементов. Поскольку каждый уровень рекурсии уменьшает размер задачи в постоянный коэффициент, общее время работы алгоритма может быть ограничено геометрической прогрессией , показывая, что оно $O(n)$ . ^[1]

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Шазель, Бернар (ноябрь 2000 г.). «Мягкая куча: примерная очередь с приоритетами и оптимальной частотой ошибок» (PDF) . Журнал АКМ . 47 (6): 1012–1027. CiteSeerX 10.1.1.5.9705 . дои : 10.1145/355541.355554 . S2CID 12556140 .
^ Jump up to: ^а ^б ^с Каплан, Хаим; Цвик, Ури (2009). «Упрощенная реализация и анализ мягких куч Шазель» . Материалы девятнадцатого ежегодного симпозиума ACM – SIAM по дискретным алгоритмам . Общество промышленной и прикладной математики. стр. 477–485. CiteSeerX 10.1.1.215.6250 . дои : 10.1137/1.9781611973068.53 . ISBN 978-0-89871-680-1 .
^ Каплан, Хаим; Тарьян, Роберт Э .; Цвик, Ури (2013). «Мягкие кучи упрощенные». SIAM Journal по вычислительной технике . 42 (4): 1660–1673. дои : 10.1137/120880185 . МР 3084181 .
^ Торуп, Миккель ; Замир, Ор; Цвик, Ури (2019). «Динамические упорядоченные наборы с приблизительными запросами, приблизительными кучами и мягкими кучами». В Байере, Кристель; Хацигианнакис, Иоаннис; Флоккини, Паола; Леонарди, Стефано (ред.). 46-й Международный коллоквиум по автоматам, языкам и программированию, ICALP 2019, 9–12 июля 2019 г., Патры, Греция . ЛИПИ. Том. 132. Замок Дагштуль – Центр информатики Лейбница. стр. 95:1–95:13. doi : 10.4230/LIPICS.ICALP.2019.95 .
^ Шазель, Бернар (2000). «Алгоритм минимального остовного дерева со сложностью типа, обратной Аккерману» . Журнал АКМ . 47 (6): 1028–1047. дои : 10.1145/355541.355562 . МР 1866456 .
^ Каплан, Хаим; Козма, Ласло; Замир, Ор; Цвик, Ури (2019). «Выбор из кучи, матриц с сортировкой по строкам и X + Y с использованием мягких куч». В Файнмане, Джереми Т.; Митценмахер, Майкл (ред.). 2-й симпозиум по простоте алгоритмов, SOSA 2019, 8–9 января 2019 г., Сан-Диего, Калифорния, США . ОАСИ. Том. 69. Замок Дагштуль – Центр информатики Лейбница. стр. 5:1–5:21. doi : 10.4230/OASICS.SOSA.2019.5 .

[c-1] Jump up to: ^а ^б ^с ^д ^и ^ж Шазель, Бернар (ноябрь 2000 г.). «Мягкая куча: примерная очередь с приоритетами и оптимальной частотой ошибок» (PDF) . Журнал АКМ . 47 (6): 1012–1027. CiteSeerX 10.1.1.5.9705 . дои : 10.1145/355541.355554 . S2CID 12556140 .

[kz-2] Jump up to: ^а ^б ^с Каплан, Хаим; Цвик, Ури (2009). «Упрощенная реализация и анализ мягких куч Шазель» . Материалы девятнадцатого ежегодного симпозиума ACM – SIAM по дискретным алгоритмам . Общество промышленной и прикладной математики. стр. 477–485. CiteSeerX 10.1.1.215.6250 . дои : 10.1137/1.9781611973068.53 . ISBN 978-0-89871-680-1 .

[ktz-3] Каплан, Хаим; Тарьян, Роберт Э .; Цвик, Ури (2013). «Мягкие кучи упрощенные». SIAM Journal по вычислительной технике . 42 (4): 1660–1673. дои : 10.1137/120880185 . МР 3084181 .

[tzz-4] Торуп, Миккель ; Замир, Ор; Цвик, Ури (2019). «Динамические упорядоченные наборы с приблизительными запросами, приблизительными кучами и мягкими кучами». В Байере, Кристель; Хацигианнакис, Иоаннис; Флоккини, Паола; Леонарди, Стефано (ред.). 46-й Международный коллоквиум по автоматам, языкам и программированию, ICALP 2019, 9–12 июля 2019 г., Патры, Греция . ЛИПИ. Том. 132. Замок Дагштуль – Центр информатики Лейбница. стр. 95:1–95:13. doi : 10.4230/LIPICS.ICALP.2019.95 .

[mst-5] Шазель, Бернар (2000). «Алгоритм минимального остовного дерева со сложностью типа, обратной Аккерману» . Журнал АКМ . 47 (6): 1028–1047. дои : 10.1145/355541.355562 . МР 1866456 .

[k2z2-6] Каплан, Хаим; Козма, Ласло; Замир, Ор; Цвик, Ури (2019). «Выбор из кучи, матриц с сортировкой по строкам и X + Y с использованием мягких куч». В Файнмане, Джереми Т.; Митценмахер, Майкл (ред.). 2-й симпозиум по простоте алгоритмов, SOSA 2019, 8–9 января 2019 г., Сан-Диего, Калифорния, США . ОАСИ. Том. 69. Замок Дагштуль – Центр информатики Лейбница. стр. 5:1–5:21. doi : 10.4230/OASICS.SOSA.2019.5 .

[1]

[2]

[3]

[4]

[5]

[6]