Heapify vs Build Heap

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?

2 Answers

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Sarah Jenkins
Author

Sarah Jenkins

Sarah Jenkins is a veteran tech journalist with over 12 years of experience covering artificial intelligence, mobile innovations, and digital ethics. Her insights have appeared in leading technology publications worldwide.