最大堆的时间复杂度是多少？

Question

我正在尝试计算整个算法的时间复杂度。是 O(nlogn) 还是 O(n)？我一直在网上搜索，有人说最大堆是 O(nlogn)，有人说是 O(n)。我正在尝试获得时间复杂度 O(n).

def max_heapify(A, i):
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i
    if left < len(A) and A[left] > A[largest]:
        largest = left
    if right < len(A) and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)


def build_max_heap(A):
    for i in range(len(A) // 2, -1, -1):
        max_heapify(A, i)
    return A

Answer 1

堆是一种支持插入和检索操作的数据结构。每个操作都有自己的运行时复杂性。

也许您正在考虑 heapsort 的运行时复杂性，这是一种使用堆的排序算法。在这种情况下，运行时复杂度为 O(n*log(n)).

Answer 2

问题中的代码重新排列数组元素，使它们满足堆属性即父节点的值大于子节点的值。 heapify操作的时间复杂度为O(n).

这是 Min-max 堆上的 [维基百科页面] 的摘录（https://en.wikipedia.org/wiki/Min-max_heap#Build

Creating a min-max heap is accomplished by an adaption of Floyd's linear-time heap construction algorithm, which proceeds in a bottom-up fashion.[10] A typical Floyd's build-heap algorithm[11] goes as follows:
function FLOYD-BUILD-HEAP (h):
    for each index i from floor(length(h)/2) down to 1 do:
        push-down(h, i)
    return h

此处函数 FLOYD-BUILD-HEAP 与您的 build_max_heap 函数相同，push-down 与您的 max_heapify 函数相同。

一个建议：你的函数命名有点混乱。您的 max_heapify 实际上并没有堆积。它只是 heapify 操作的一部分。更好的名称可以是 push_down（在维基百科中使用）或 fix_heap.

最大堆的时间复杂度是多少？

What's the time complexity for max heap?

python

heap

time-complexity