比较从键列表构建整个 binayHeap 的方法

Question

正在阅读有关构建二叉堆的 post。我对方法 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() 会负责恢复堆的属性每 time.Also，我的方法与他的 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

您的分析是正确的。笔者一头雾水。他说：

To finish our discussion of binary heaps, we will look at a method to build an entire heap from a list of keys. The first method you might think of may be like the following. Given a list of keys, you could easily build a heap by inserting each key one at a time. Since you are starting with a list of one item, the list is sorted and you could use binary search to find the right position to insert the next key at a cost of approximately O(logn) operations. However, remember that inserting an item in the middle of the list may require O(n) operations to shift the rest of the list over to make room for the new key. Therefore, to insert n keys into the heap would require a total of O(nlogn) operations.

该段中对二分查找的讨论无关紧要。在创建二叉堆时不需要进行二分查找，并且在向二叉堆中插入一个项目时，您不需要执行 O(n) 操作来为新项目创建 space。二叉堆结构的全部意义在于避免那种昂贵的插入。

稍微改写，删掉作者写的不相关的部分：

To finish our discussion of binary heaps, we will look at a method to build an entire heap from a list of keys. The first method you might think of may be like the following. Given a list of keys, you could easily build a heap by inserting each key one at a time, at a cost of O(log n) operations per insertion. Therefore, to insert n keys into the heap would require a total of O(n log n) operations.

比较从键列表构建整个 binayHeap 的方法

Comparing methods to build an entire binayHeap from a list of keys

heap

binary-heap

python-3.x