Я прохожу практический экзамен, который у меня на экзамене, который я сдаю завтра.В разделе true / false есть следующее утверждение:
Последовательность значений вставляется в совершенно новую кучу, не содержащую каких-либо предыдущих значений.Значения могут быть вставлены в кучу в разных порядках;что из следующего является правильным в отношении того, что произойдет?
BigTheta (log (n)) всегда будет вставлять каждое значение (где n - количество элементов, находящихся в настоящий момент в куче), независимо отзначения, которые вставляются в кучу.
Ответ - ЛОЖЬ.Но я не понимаю почему.Насколько я понимаю, BigTheta будет log (n), потому что алгоритм вставки для кучи включает в себя помещение элемента, который мы вставляем, в следующую позицию в куче (самый правый слот на самом низком уровне), а затем сравнение этого вставленного значения с егопредки (и обмен по мере необходимости).
Разве это не должно в худшем случае вести лог (n) сравнений?Так как дерево имеет высоту log (n)?Если так, то почему не ответ BigTheta (log (n))?
Спасибо