Heapify

In the context of the heap data structure, heapify is an operation that ensures the heap property is maintained. The heap property states that for a max heap, for example, the parent node must be greater than or equal to its children.

Heapify is commonly used after an element is inserted or removed from a heap to rearrange the elements and maintain the heap property.

To perform heapify, we start from the last non-leaf node and compare it with its children. If the parent node is not greater than its children, we swap the parent node with the largest child. We then recursively perform heapify on the affected child subtree.

Here is an example of heapify in action using Java:

1class Main {
2  public static void main(String[] args) {
3    int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
4    heapify(arr);
5
6    System.out.println("Heapified array: ");
7    for (int num : arr) {
8      System.out.print(num + " ");
9    }
10  }
11
12  public static void heapify(int[] arr) {
13    int n = arr.length;
14
15    for (int i = n / 2 - 1; i >= 0; i--) {
16      heapifyUtil(arr, n, i);
17    }
18  }
19
20  public static void heapifyUtil(int[] arr, int n, int i) {
21    int largest = i;
22    int left = 2 * i + 1;
23    int right = 2 * i + 2;
24
25    if (left < n && arr[left] > arr[largest]) {
26      largest = left;
27    }
28
29    if (right < n && arr[right] > arr[largest]) {
30      largest = right;
31    }
32
33    if (largest != i) {
34      int temp = arr[i];
35      arr[i] = arr[largest];
36      arr[largest] = temp;
37
38      heapifyUtil(arr, n, largest);
39    }
40  }
41}

In this example, we have an array arr containing elements in random order. We call the heapify function, which rearranges the elements to satisfy the heap property. The resulting heapified array is then printed.

Heapify is an important operation in heap data structures as it allows efficient insertion and deletion operations while maintaining the desired heap property.

xxxxxxxxxx

}

class Main {

  public static void main(String[] args) {

    // replace with your Java logic here

    int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};

    heapify(arr);

​

    System.out.println("Heapified array: ");

    for (int num : arr) {

      System.out.print(num + " ");

    }

  }

​

  public static void heapify(int[] arr) {

    int n = arr.length;

​

    for (int i = n / 2 - 1; i >= 0; i--) {

      heapifyUtil(arr, n, i);

    }

  }

​

  public static void heapifyUtil(int[] arr, int n, int i) {

    int largest = i;

    int left = 2 * i + 1;

    int right = 2 * i + 2;

​

    if (left < n && arr[left] > arr[largest]) {

      largest = left;

    }

​