'heapify VS build heap

Can you please confirm the meaning of the concept 'heapify', the source I am learning from says that heapify is building a heap from an array (from scratch)

This is how I understand after googling several resources

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 is not:

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

Is this right?

algorithmdata-structuresheap


Solution 1:[1]

Basically, heapify is an algorithm used to re-arrange the heap if the root node violates the heap property (child subtrees must be heaps!). It's a vital part of building a heap, inserting or deleting a top node from the heap.

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)

Here you describe how heapify is used if the top element is removed. Yep, it's a valid case because you need to keep your max/min element at the top (depending on whether it's a max heap or a min heap).

Heapify is not:

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

You're right, it's not. As said before, heapify is just a way to maintain heap properties after performing operations on it.

You use heapify for building a heap to make sure your resulting data structure meets heap requirements. For example, given you need to build a min heap from an array, you can do it as follows:

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]

As you can see, even though heapify is actively used for building a heap, we cannot say that building a heap is heapify. It's just an essential part of the process.

Solution 2:[2]

Heapify is the process of converting a binary tree into a Heap data structure in O(N).

Heapify starts from leaf nodes and checks if each subtree is a heap or not. If not heap, check downward and make it adjust it to make a heap. we repeat these steps for all nodes until we reach the root

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 Yilmaz

Related Questions