Algorithm of the day -

The Heapify Algorithm

Summary

The Heapify algorithm is a process used to maintain the heap property in a binary heap data structure, ensuring that the parent node is either greater than (or less than) its child nodes, which is essential for efficient sorting and priority queuing.

Use Case

The Heapify algorithm is used in the Heap Sort algorithm to build a max heap from an unsorted array, which can then be used to efficiently sort the array in ascending order.

Steps

  1. Start at the root node of the heap.
  2. Compare the root node with its child nodes.
  3. If the root node is smaller (or larger) than its child nodes, swap it with the smallest (or largest) child node.
  4. Repeat the process recursively for the affected sub-tree until the heap property is restored.

Complexity

The time complexity of the Heapify algorithm is O(log n) and the space complexity is O(1), making it efficient for large datasets.

Code Example

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[i] < arr[left]:
        largest = left
    if right < n and arr[largest] < arr[right]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)