Читая публикацию о создании двоичной кучи. Я запутался в подходе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)
Я не понимал, почему ему нужно выполнять двоичный поиск, чтобы найти правильную позицию для вставки следующей, когда я могу просто использовать вставку() для каждой клавиши за раз, а 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]
Пожалуйста, предложите, где я ошибаюсь и что мне не хватает?
