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

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

0 голосов
/ 22 ноября 2018

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

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

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

1 Ответ

0 голосов
/ 23 ноября 2018

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

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

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

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

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

...