Сравнение методов построения целого binayHeap из списка ключей

Question

Читая пост о построении двоичной кучи. Я запутался в подходе1.

Подход автора1(O(n*log n)):

• Учитывая список ключей, создайте двоичную кучу, вставляя каждый ключ по одному.

• Поскольку вы начинаете со списка из одного элемента, список сортируется, и вы можете использовать бинарный поиск, чтобы найти правильную позицию для вставки следующего ключа, затратив приблизительно O(logn) операций.

• Однако для вставки элемента в середину списка может потребоваться O(n) операций для смещения остальной части списка, чтобы освободить место для нового ключа.

• Следовательно, для вставки n ключей в кучу потребуется всего O(nlogn) операций.

`

class BinHeap:
    def __init__(self):
        self.heapList = [0] 
        self.currentSize = 0

def percUp(self,i):
    while i // 2 > 0:
      if self.heapList[i] < self.heapList[i // 2]:
         tmp = self.heapList[i // 2]
         self.heapList[i // 2] = self.heapList[i]
         self.heapList[i] = tmp
      i = i // 2

def insert(self, k):
    self.heapList.append(k)
    self.currentSize = self.currentSize + 1
    self.percUp(self.currentSize)

Я не понимаю, почему ему нужно выполнить бинарный поиск, чтобы найти правильную позицию для вставки следующей, когда я могу просто использовать insert() для каждого ключа за раз, а percUp() позаботится о восстановлении свойства кучи каждый раз Также, чем мой подход отличается от его подхода O (n * log n):

def method1(list):

    newHeap = BinHeap()
    for key in list:
        newHeap.insert(key)

    return newHeap.heapList

list_keys= [9,6,5,2,3]
print('Method-1', method1(list_keys)[1:])

и получить результат

Method-1 [2, 3, 6, 9, 5]

Пожалуйста, предложите, где я иду не так и чего мне не хватает?

Answer 1

Ваш анализ верен. Автор в замешательстве. Он говорит:

Чтобы закончить наше обсуждение бинарных куч, мы рассмотрим метод построения всей кучи из списка ключей. Первый способ, о котором вы можете подумать, может быть следующим. Имея список ключей, вы можете легко построить кучу, вставляя каждый ключ по одному. Поскольку вы начинаете со списка из одного элемента, список сортируется, и вы можете использовать бинарный поиск, чтобы найти правильную позицию для вставки следующего ключа, затратив приблизительно O(logn) операций. Однако помните, что для вставки элемента в середину списка могут потребоваться операции O(n), чтобы переместить остальную часть списка, чтобы освободить место для нового ключа. Следовательно, для вставки n ключей в кучу потребуется всего O(nlogn) операций.

Обсуждение бинарного поиска в этом параграфе не имеет значения. При создании двоичной кучи нет необходимости выполнять бинарный поиск, и при вставке элемента в двоичную кучу не возникает ситуации, когда вам нужно выполнить O(n) операций, чтобы освободить место для нового элемента. Весь смысл структуры двоичной кучи состоит в том, чтобы избежать такого типа дорогостоящей вставки.

Немного переписать и отредактировать несущественные части того, что написал автор:

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