Сложность времени вставки в кучу

Question

Я стараюсь в основном понять аргументы за большой о и омега вставляя новый элемент в кучу. Я знаю, что могу найти ответы онлайн, но мне очень нравится иметь полное понимание, а не просто находить ответы онлайн и просто запоминать вслепую.

Так, например, если мы имеем следующую Heap (Представлял в формате массива)

[8,6,7,3,5,3,4,1,2] 

Если мы решили вставить новый элемент «4» наш массив будет выглядеть, как это сейчас

[8,6,7,3,5,3,4,1,2,4] 

Он будет помещен в индекс 9, и поскольку это 0-й индексный массив, его родителем будет индекс 4, который является элементом 5. В этом случае нам не нужно ничего делать, потому что 4 - это < 5 и не нарушает двоичную кучу имущество. Так что лучший пример OMEGA (1).

Однако, если новый элемент, который мы вставляем, равен 100, тогда нам нужно будет вызвать функцию max-heapify, которая имеет время работы O (Log n), и поэтому в худшем случае вставка нового элемента в кучу принимает O (Log n) ,

Может кто-то исправить меня, если я ошибаюсь, потому что я не уверен, что мое понимание или рассуждение 100%?

Answer 1

Да, вы правы в лучшем случае. И для наихудшего времени работы вы также правы, что это Theta (lg n), и причина в том, что ваша куча всегда считается БАЛАНСИРОВАННОЙ, т. Е. Каждый набор узлов уровня высоты заполнен, за исключением нижнего уровня , Поэтому, когда вы вставляете элемент на нижнем уровне и свопите с одного уровня на следующий уровень в своей куче, количество узлов на этом уровне сокращается примерно наполовину, и поэтому вы можете делать это только с помощью swap log_2 (n) = O (lg n) раз, прежде чем вы окажетесь в корневом узле (т.е. на уровне в верхней части кучи, имеющей только один узел). И если вы вставляете значение, которое находится в верхней части кучи, сначала в нижней части кучи, тогда вам действительно придется выполнять в основном log_2 (n) свопы, чтобы получить элемент вверху кучи, где он принадлежит. Таким образом, число свопов в худшем случае - Theta (lg n).

Answer 2

Ваше понимание верности. Поскольку куча имеет полную двоичную структуру дерева, ее высота = lg n (где n - нет элементов). В худшем случае (элемент, вставленный внизу, должен быть заменен на каждом уровне снизу вверх до корневого узла, чтобы сохранить свойство кучи), требуется 1 своп на каждом уровне. Таким образом, максимальное количество раз этого свопа - log n. Следовательно, вставка в кучу принимает время O (log n).