heapify VS 构建堆

Question

请确认概念的含义 'heapify'，我正在学习的来源说 heapify 是从数组（从头开始）构建堆

这是我在谷歌搜索几个资源后的理解

Heapify 是：

在弹出堆的顶部节点并将最后一个节点移动到顶部之后，我们从上到下重新排列树，使其再次成为一个堆（我们堆化）
heapify 时间复杂度 O(log n)

Heapify 不是：

从数组创建堆，这是一个自下而上的操作，时间复杂度为 O(n)

这样对吗？

Answer 1

基本上，heapify是一种算法，用于如果根节点违反堆属性（子树必须是堆！).它是构建堆、从堆中插入或删除顶部节点的重要部分。

Heapify is:

after we popped the top node of the heap and we moved the last node to the top then we rearrange the tree from top-to-bottom so it is a heap again (we heapify)

heapify time complexity O(log n)

这里您将描述如何在删除顶部元素时使用 heapify。是的，这是一个有效的案例，因为您需要将 max/min 元素保持在顶部（取决于它是最大堆还是最小堆）。

Heapify is not:

creating a heap from an array which is a bottom-up operation with a time complexity of O(n)

你说得对，事实并非如此。如前所述，heapify只是一种在对其执行操作后维护堆属性的方法。

您使用 heapify 构建堆以确保生成的数据结构满足堆要求。例如，假设您需要从一个数组构建一个最小堆，您可以按如下方式进行：

def min_heapify(arr, index):
    size      = len(arr)
    new_index = index
    left      = index * 2 + 1
    right     = index * 2 + 2

    if (left < size and arr[left] < arr[new_index]):
        new_index = left

    if (right < size and arr[right] < arr[new_index]):
        new_index = right

    if (new_index != index):
        arr[index], arr[new_index] = arr[new_index], arr[index]
        min_heapify(arr, new_index)

array = [5, 4, 3, 2, 1]

size = len(array)
for i in range((size//2) - 1, -1, -1):
    min_heapify(array, i)

print (array)

[1, 2, 3, 5, 4]

如你所见，即使heapify积极用于建堆，我们也不能说建堆就是heapify。这只是该过程的重要组成部分。

Answer 2

Heapify是O(N)中将二叉树转换成Heap数据结构的过程。

Heapify 从叶节点开始，检查每个子树是否是堆。如果不是堆，则向下检查并调整它以形成堆。我们对所有节点重复这些步骤，直到我们到达根

heapify VS 构建堆

heapify VS build heap

algorithm

heap

data-structures