Почему deleteMin из кучи берет O(logn)?

Question

На слайде лекций моего класса у меня есть куча, и у нее есть метод, называемый deleteMin(). Что он делает, он удаляет минимальное значение в куче. И это говорит, что требуется O(logn).

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

Но почему это говорит O(logn)?

Answer 1

Потому что, если вы вытащите верхний узел, вам придется преобразовать оставшиеся две кучи в одну. Чтобы сохранить свойства кучи, вы должны сделать самый правый элемент в нижней строке корневым, а затем downheap, что занимает O(log n). Я думаю, что вы рассматриваете лучший способ добиться этого, но вышеупомянутый метод в настоящее время является самым быстрым методом. Надеюсь, этот пост помог вам!