Lecture 329:- Heapify - Faster Method for creating Heap

The "Heapify" method is an optimized approach to create a heap from an input array in-place. It efficiently rearranges the elements of the array to form a heap, without the need to insert elements one by one.

Here's how the Heapify method works:

1. Start from the last non-leaf node of the array. (A binary heap is a complete binary tree, and all nodes after the last non-leaf node are leaf nodes, so they automatically satisfy the heap property.)
2. For each non-leaf node, compare it with its children (left child and right child).
3. Swap the node with its larger child (for max heap) or smaller child (for min heap) if the heap property is violated.
4. Move to the previous non-leaf node and repeat the process until the root of the heap is reached.

This approach ensures that at each step, the subtree rooted at a node satisfies the heap property, leading to a valid heap when the process is completed.

Here's a C++ implementation of the Heapify method for creating a max heap:

cppCopy code

#include <iostream> #include <vector> using namespace std; // Function to heapify a subtree rooted with the node at index 'i' in a max heap void maxHeapify(vector<int>& arr, int n, int i) {    int largest = i;    int leftChild = 2 * i + 1;    int rightChild = 2 * i + 2;    if (leftChild < n && arr[leftChild] > arr[largest])        largest = leftChild;    if (rightChild < n && arr[rightChild] > arr[largest])        largest = rightChild;    if (largest != i) {        swap(arr[i], arr[largest]);        maxHeapify(arr, n, largest);    } } // Function to create a max heap from an input array using the Heapify method void buildMaxHeap(vector<int>& arr) {    int n = arr.size();    // Start from the last non-leaf node and heapify each non-leaf node in reverse order    for (int i = n / 2 - 1; i >= 0; i--)        maxHeapify(arr, n, i); } // Function to display the elements of the array void display(const vector<int>& arr) {    for (int val : arr)        cout << val << " ";    cout << endl; } int main() {    vector<int> arr = {12, 11, 13, 5, 6, 7};    cout << "Original Array: ";    display(arr);    buildMaxHeap(arr);    cout << "Max Heap: ";    display(arr);    return 0; }

In this program, the maxHeapify function is used to maintain the heap property of a subtree rooted at a given index in a max heap. The buildMaxHeap function uses the Heapify method to create a max heap from the input array. Finally, the display function is used to display the elements of the max heap.

The Heapify method is more efficient than inserting elements one by one to create a heap, as it has a time complexity of O(n) compared to O(n*log n) for inserting n elements.