# Heapify

- This chapter uses Max Heap, but the same concept could be applied on Min Heap as well by simple tweaking of logic.

At the very outset, even before going into more details, I want to make it clear that

*does not mean building a heap from a RANDOM array.*

**Heapify***operation can be done on a segment of an array arr[i...(n - 1)] if and only if elements in array segment arr[(i + 1)...(n - 1)] maintains*

**Heapify****heap property**already, which means for a max heap:

`arr[j] > arr[2 * j + 1] and arr[j] > arr[2 * j + 2]`

for an index j where
j > i and j < n. After the heapify operation completes on arr[i...(n - 1)], arr[i] would
contain the element which has the max value among all the elements in arr[i...(n - 1)] and
arr[i...(n - 1)] would be a complete representation of a max heap. Now just by giving it a little thought,
you would be able to figure that: **given a random array you could build a heap out of it just by executing the Heapify operation on arr[n - 1], followed by arr[n - 2] and so on all the to arr[0]. n = total number of elements in arr.**let'sthe last non-leaf node :

```
Now a very important observation: to call Heapify
on an array segment, all the elements in the segment except the first one
MUST maintain heap property. Now
notice that the leaf nodes already exhibit heap property, since a leaf
on its own is like an one node tree and an one node tree is a heap. So all the leaf nodes
already maintain heap property.
```

Index of Last non-leaf node = parent of last-node. = parent of node at (n-1)th index. = Node at index ((n-1) - 1)/2. = (n/2) - 1.

```
So, if total number of nodes = n, then number
of leaf nodes = ceiling(n / 2), and number of non-leaf nodes = floor(n / 2).
You could also deduce this relation just
by reminding yourself the fact that heaps are COMPLETE BINARY TREES.
```

**So, we need to call heapify on elements from arr[n / 2] to arr[0].**

Enough of theory. Let's look at the code below to have clear understanding of

`MAX_HEAPIFY`

and `BUILD_MAX_HEAP`

.
Login to Access Content

#### Time Complexity:

**MAX_HEAPIFY:**O(height of the heap) = O(log

_{2}N), where N = total number of elements in the heap.

**BUILD_MAX_HEAP:**O(Nlog

_{2}N) since MAX_HEAPIFY is called O(N) times.