steps:

• increase the heap size by 1.
• Insert the new element at the end of the Heap.
• heapify this newly inserted element following a bottom-up approach.

Suppose the Heap is a Max-Heap as:

The new element to be inserted is 15.

steps:
Step 1: Insert the new element at the end.

Step 2: Heapify the new element following bottom-up
approach.
-> 15 is greater than its parent 4, swap them.

-> 15 is again greater than its parent 12 , swap them.
Therefore, the final heap after insertion is

and this follows the max heap properties.

implementation (for max heap):
arr[] is an array
n is the size
i is the node to be heapified
key is  the inserted element.

in c++:

```void maxheapify(int arr[], int n, int i)
{
// Find parent
int parent = (i - 1) / 2;

if (parent >= 0) {

// For Max-Heap
// If current node is greater than its parent
// Swap both of them and call heapify again
// for the parent
if (arr[i] > arr[parent]) {
swap(arr[i], arr[parent]);

// Recursively heapify the parent node
maxheapify(arr, n, parent);
}
}
}

// Function to insert a new node to the Heap
void insertNode(int arr[], int& n, int Key)
{
// Increase the size of Heap by 1
n = n + 1;

// Insert the element at end of Heap
arr[n - 1] = Key;

// Heapify the new node following a
// Bottom-up approach
maxheapify(arr, n, n - 1);
}
```

java:

```      private void maxheapify(int i)
{
int n=size+1 ;

// Find parent
int parent = (i - 1) / 2;

if (parent >= 0) {

// For Max-Heap
// If current node is greater than its parent
// Swap both of them and call heapify again
// for the parent
if (arr[i] > arr[parent]) {
int temp=arr[parent];
arr[parent]=arr[i];
arr[i]=temp;
// swap
// Recursively heapify the parent node
maxheapify(parent);
}
}
}

// Function to insert key to heap
// Inserts a new element to max heap
public void insert(int element)
{
arr[++size] = element;
if(size>0)
heapify(size);
}

```

similar procedure for the min heap.

darkmode