Спаривание кучи - O (1) для клавиши уменьшения?

Я работаю над заданием для одного из своих курсов, и один вопрос требует показать, что операция уменьшения ключа для кучи сопряжения занимает O (1) времени.

Очевидно, что если у вас есть указатель на ключ, который вы хотите уменьшить, то операция займет время O(1) (просто удалите ссылку, измените значение ключа, затем объедините).

Однако нигде в задании не сказано, что нам дан указатель на ключ. Если нам не дан указатель, то ключ уменьшения не может занять O(1) времени (вам придется сначала искать ключ в куче, а это не занимает постоянное время). Я посмотрел литературу, и все говорят, что клавиша уменьшения занимает O (logn) времени.

Я что-то упустил здесь?


heap amortized-analysis pairing-heap
person Asool    schedule 19.05.2016    source источник
comment
Нет, вы ничего не упускаете. Если у вас нет ссылки на узел, вам придется выполнить проход O (n), чтобы найти его.   -  person Jim Mischel    schedule 08.08.2016

Ответы (1)


arrow_upward
2
arrow_downward

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

person templatetypedef    schedule 13.06.2016
comment
Это странно, потому что в оригинальной статье есть очень простая операция, которая полностью локальна (она зависит от максимум 3 узлов, независимо от размера кучи). Однако это платный контент :-(. Я предполагаю, что вы читали его, можете ли вы хотя бы сказать, какой вариант был проанализирован - один с указателями (родительский + левый дочерний + правый родственный) или один с (левый одноуровневый/родительский указатель + правый брат), и сравнивал ли ключ уменьшения свое значение с родителем или нет (в оригинале это не так). - person greenoldman; 22.12.2018
comment
Вы правы в том, что наихудшее время выполнения ключа уменьшения — O(1). Однако при выполнении операции уменьшения ключа куча реструктурируется таким образом, что последующие операции удаления мин выполняются медленнее. Амортизированный анализ парной кучи работает путем обратного начисления работы от удаления-минуты обратно к предыдущим операциям, и при этом амортизированная стоимость ключа уменьшения составляет Омега (log log n). - person templatetypedef; 22.12.2018