Амортизированный анализ и конкурс Questiosn, есть какие-нибудь проблемы?

Question

Я столкнулся с вопросом местного конкурса следующим образом.

Если на пустом MIN-Heap мы делаем n произвольный insert а также delete операции, (с заданным местоположением удаления в мин-куче). что amortized analysis за insert а также delete?

I) вставить O (log n), удалить O (1)

II) вставить O (log n), удалить O (log n)

III) вставить O(1), удалить O (1)

IV) вставить O(1), удалить O (log n)

Я думаю, что это проблема с этими вопросами, потому что тип кучи не определен. Я читал в Google, что у нас есть вариант (1) и (4) для некоторой кучи. с экспертной точки зрения мы можем сказать с этим вопросом can we select all options as True?

Answer 1

Вы правы - вопрос не правильный. Min heap - это абстрактная структура данных, которая поддерживает операции push и popMin и может быть реализована многими различными способами. В зависимости от реализации сложность операций будет разной. Также удаление в данном месте не является операцией кучи класса min. Если в вопросе не было большего контекста, он не был четко определен.