二进制最大堆时间复杂性

将无序数组转换为二进制堆 在正确的位置 是O(n)运算。所以很明显,如果您有一堆要构建堆的项,您可以将它们放在一个数组中,然后调用一个将数组重新排列为堆的方法。该方法通常称为 BuildHeap 或 Heapify .

如果您构建一个空堆,然后向其中添加n个项,则插入每个项需要O(logn)个操作,从而占用O(logN)个运行时间。

维基百科的文章提出了一种在O(n)中构建堆的算法。当然,您可以在O(n log n)上构建它。

所有其他修改操作都需要O(log n)。

从下到上堆积的时间复杂度为 O(n) (使用给定的arry堆积)

从上到下堆积的时间复杂度为 O(nlogn) (一次创建一个节点的堆)

你可以通过一个接一个地插入n个元素来构建一个二进制堆,这意味着运行时是O(n log(n)),假设堆属性对所有高度为h的子树都有效。你可以使用自底向上的构造来构建存储n个键的堆,其中包含log(n个阶段)。由于每个节点最多由两个代理路径遍历,因此代理路径上的节点总数为O(n)。因此,自下而上的堆构造在O(n)时间内运行。